我正在做一个比较应用程序，为了用户体验，我想实现一个进度条让用户看到。现在，根本不可能确切地知道需要进行多少次比较，所以在每次比较之后获得最小和最大比较的范围是理想的，因为我可以动态地向用户保证他们正在接近他们的目标。
我使用的算法是this算法的TypeScript版本，增加了一个函数calculateMinMax()，它返回给定长度的最小值和最大值。经过一段时间（令人尴尬的时间），我发现最小比较值总是C(n) = Math.floor(Math.log2(n)) + C(n - 1)，而最大比较值总是C(n) = Math.ceil(Math.log2(n)) + C(n - 1)。代码如下：

class PrefList {
    size: number
    items: { item: number, equals: number[] }[] = [{ item: 0, equals: [] }]
    current = { item: 1, try: 0, min: 0, max: 1 }
    iteration: number = 0
    estimated: { min: number, max: number } = { min: 0, max: 0 }

    constructor(n: number)
    constructor(n: Array<any>)
    constructor(n: number | Array<any>) {
        this.size = (typeof n == "number") ? n : n.length

        const [min, max] = this.calculateMinMax(this.size)
        this.estimated = {min, max}
    }

    addAnswer(pref: -1 | 0 | 1): void {
        this.iteration++
        if (pref == 0) {
            this.items[this.current.try].equals.push(this.current.item)
            this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
        } else {
            if (pref == -1) this.current.max = this.current.try
            else this.current.min = this.current.try + 1
            if (this.current.min == this.current.max) {
                this.items.splice(this.current.min, 0, { item: this.current.item, equals: [] })
                this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
            }
        }
    }

    getQuestion(): { a: number, b: number } {
        if (this.current.item >= this.size) return null
        this.current.try = Math.floor((this.current.min + this.current.max) / 2)
        return ({ a: this.current.item, b: this.items[this.current.try].item })
    }

    getOrder() {
        var index = []
        for (var i in this.items) {
            index.push(this.items[i].item)
            for (var j in this.items[i].equals) {
                index.push(this.items[i].equals[j])
            }
        }
        return (index)
    }

    calculateMinMax(v: number): [number, number] {
        if (v <= 1) return [0, 0]
        const val = Math.log2(v)
        const rest = this.calculateMinMax(v - 1)
        return [Math.floor(val) + rest[0], Math.ceil(val) + rest[1]]
    }
}

现在，这个函数在初始化类时工作，但这就是它的作用。我尝试了多种方法来处理每一步的最小值和最大值的更新（每次进行比较时），但我无法弄清楚。我很确定选择第一个和第二个之间有联系。选择第二个，因为在每次比较中选择第一个将给你给予最小的比较量，而在每次比较中选择第二个将给你给予最大的比较量，但这就是我所得到的。我真的不知道该怎么办。任何和所有的帮助是赞赏。
下面是一个比较的例子（原始测试的稍微修改版本）。在这个例子中，你有一个数组，里面有8种水果，你可以在每种水果中选择一种。下面是测试代码：

var array = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry"]

var t = new PrefList(array.length), q
while (q = t.getQuestion()) {
    console.log(t.iteration + ". " + array[q.a] + " or " + array[q.b] + "?")
    const response = prompt("")
    var answer = parseInt(response)
    console.log("→ " + [array[q.a], "whatever", array[q.b]][answer + 1])
    t.addAnswer(answer as -1 | 1)
    console.log("")
}

var index = t.getOrder()
console.log("\nLIST IN ORDER:")
for (var i in index) console.log("\t" + (parseInt(i) + 1) + ". " + array[index[i]])

当运行上面的代码时，你可以通过输入1来选择左边的选项，通过输入-1来选择右边的选项（除了第一个选项，在这种情况下，1对应于右边的项目，-1对应于左边的项目）。

我想通了。为了在当前步骤中找到最小值和最大值比较，必须存储在前面步骤中进行的比较，并在计算最小值和最大值时使用它们。

说明

为了更好地理解这一点，我们可以分解最小值和最大值函数：

function calculateMinMax(v: number): [number, number] {

    // Return [0, 0] since log2(1) = 0
    if (v <= 1) return [0, 0]

    // Get the log2 of the current number
    const val = Math.log2(v)

    // Recursive call (can be ignored for now)
    const rest = this.calculateMinMax(v - 1)

    // Get the minimum amount of comparisons for this number
    const minimum = Math.floor(val)

    // Get the maximum amount of comparisons for this number
    const maximum = Math.ceil(val)

    // Return the sum of the minimum and the rest (from recursive call), and the sum of the maximum and the rest (from recursive call)
    return [
        minimum + rest[0],
        maximum + rest[1]
    ]
}

现在，我们的最小值和最大值有不同值的原因是因为一个是向下舍入，而另一个是向上舍入。这意味着某个数字在移动到下一个之前可能有x或x + 1的比较量（除非它是2的平方积，在这种情况下，log2(n)是整数，因此只有x）。两个值的变化总是来自于每个数字的比较差异。这是唯一的变量，波动我们的可能性和范围。
那么，我们能做些什么来对抗它呢？简单，用现实的数字。在计算最小值和最大值时，我们使用理论值。
让我们假设我们在一个16个元素的数组上运行这段代码，所有的答案都是1（所以a > b，b > c，等等）。假设我们正在比较第九个元素。如果进行计算，我们将看到log2(9) = 3.1699250014，这意味着我们对第9个元素的最小比较是3，最大是4。这很好，但如果我们在第12个元素上呢？好吧，因为我们总是选择1作为答案，所以我们知道第9个元素在进入下一个之前总共比较了3次。有了这些信息，我们可以摆脱最小/最大值，简单地用现有的值代替它们，因为我们不再需要依赖于理论，我们已经得到了答案。
要做到这一点，只需跟踪每个元素在进入下一个元素之前进行了多少次比较。如何做到这一点取决于你，但为了解释起见，我将创建一个名为getTotalComparisons(n)的虚构函数，它将返回数字n或null的总比较。现在，我们可以去掉最小值和最大值，但为了简单起见，我将简单地将val值替换为我们的总比较，因为整数向上或向下舍入将始终具有相同的数字。下面是它的样子：

function calculateMinMax(v: number): [number, number] {

    // Return [0, 0] since log2(1) = 0
    if (v <= 1) return [0, 0]

    // Get the total comparisons of the current number, if any
    const totalComparisons = this.getTotalComparisons(v)

    // If `totalComparison` is not null, set `val` to `totalComparison`, else set `val` to log2 of the current number
    const val = (totalComparisons) ? totalComparisons : Math.log2(v)

    // Recursive call (can be ignored for now)
    const rest = this.calculateMinMax(v - 1)

    // Get the minimum amount of comparisons for this number
    const minimum = Math.floor(val)

    // Get the maximum amount of comparisons for this number
    const maximum = Math.ceil(val)

    // Return the sum of the minimum and the rest (from recursive call), and the sum of the maximum and the rest (from recursive call)
    return [
        minimum + rest[0],
        maximum + rest[1]
    ]
}

就这样这将返回基于当前步骤的最小和最大比较量。您可以在每个答案之后（或之前）运行此函数，以了解可能还剩多少个问题。

解决方案

下面是修改后的代码，修改了calculateMinMax类以允许每步结果：

class PrefList {
    size: number
    items: { item: number}[] = [{ item: 0 }]
    current = { item: 1, try: 0, min: 0, max: 1 }
    iteration: number = 0
    comparisonValues: {[key: number]: number} = {}

    constructor(n: number)
    constructor(n: Array<any>)
    constructor(n: number | Array<any>) {
        this.size = (typeof n == "number") ? n : n.length
    }

    addAnswer(pref: -1 | 1): void {
        this.iteration++
        if (!this.comparisonValues[this.current.item]) this.comparisonValues[this.current.item] = 0
        this.comparisonValues[this.current.item]++
        
        if (pref == -1) this.current.max = this.current.try
        else this.current.min = this.current.try + 1

        if (this.current.min == this.current.max) {
            this.items.splice(this.current.min, 0, { item: this.current.item})
            this.current = { item: ++this.current.item, try: 0, min: 0, max: this.items.length }
        }
    }

    getQuestion(): { a: number, b: number } {
        if (this.current.item >= this.size) return null
        this.current.try = Math.floor((this.current.min + this.current.max) / 2)
        return ({ a: this.current.item, b: this.items[this.current.try].item })
    }

    getOrder() {
        var index = []
        for (var i in this.items) {
            index.push(this.items[i].item)
        }
        return (index)
    }

    calculateMinMax(v: number = this.size) {
        if (v <= 1) return [0, 0]

        const comparisons = this.comparisonValues[v - 1]
        const val = (comparisons && this.current.item != v - 1) ? this.comparisonValues[v - 1] : Math.log2(v)
        const rest = this.calculateMinMax(v - 1)

        return [Math.floor(val) + rest[0], Math.ceil(val) + rest[1]]
    }
}

javascript 如何使用偏好算法获得每一步的最小和最大比较可能性？

1条答案

说明

解决方案

相关问题

热门标签

最新问答