algorithm - 常用和最近使用的商品排名算法

Question

我正在寻找一种排序算法，该算法将按使用量以及最新使用量对项目（文件，应用程序，访问的网站...）进行排序。

例如，在应用程序启动器中，用户键入应用程序名称的一些短前缀，将对符合条件的应用程序进行排名。应用程序A是用户最喜欢的应用程序，并且使用频率很高，但是现在他经常使用应用程序B，有时甚至使用应用程序A。应用程序A的启动时间比应用程序B多，但上次使用情况B却比应用程序A多。

因此应用B在应用A之前排名。

此外，如果应用C要超越应用B，则必须（最近一次）更频繁地使用它，但是对于应用A而言，它不需要太多使用，因为它是用户最喜欢的应用，并且过去有比其他应用更多的用途。

我不知道这是否是我想要的很好的解释，但我希望有人能理解。

Answer 1

我认为您可以使用cache replacement policy的实现来实现。

这些算法帮助计算机处理器（CPU）确定将主存储器（RAM）的哪些部分（“页面”）保留在缓存（L1，L2等）中-CPU可以比RAM更快地访问它们。但是它们可以很容易地适应您的问题。

一种按最新用法对项目进行排序的算法将类似于缓存策略LRU，该策略在缓存已满时会过期/替换“最近最少使用”页面。

一种按最常用的使用方式对项目进行排序的算法（此处的“常用”实际上表示“使用次数”）将类似于缓存策略LFU，后者在缓存已满时会过期/替换“最不常用”页面。

有几种策略以您所请求的方式显式或隐式地结合了这两个概念。有些还涉及“时间”（就实际计算机时钟时间而言，或者只是页面请求的递增计数器等），以获得对页面访问的“年龄”或“频率”的更好理解（与单纯的使用次数相反） ）。

这些变得稍微复杂些，并且难以实现，尤其是在您需要非常高效的算法的情况下。但是，对于大多数与用户界面相关的用途，即使效率低下的算法也应该足够快，因为项目数量很少，用户很少会修改列表。

LRFU（最近/最不常用）策略是一个可能对您有用的算法示例，该策略根据结合了新近度和使用频率的公式直接寻求将LRU和LFU组合以使页面过期。您可以在上面列出的同一页上找到对此的引用。您也可以在scholarly article上看到它的报告位置。

本文使用堆和链表数据结构的组合来实现它，并且包含一些实现的伪代码。

为了您的使用，您可能相当容易地编写了一个简单得多但效率较低的算法。

例如，您可以简单地存储具有2个属性的对象数组：


价值（您关心的事情-例如网站或文件名等）
分数（在下面讨论-在文章中称为“ CRF”）


只要用户选择了值，就可以如下修改列表：


通过将每个分数乘以恒定的权重因子USAGE_WEIGHT（介于0.5和1.0之间的数字，将在下面进行更多讨论）来更新列表中所有现有项目的分数。
搜索列表以查看是否已存在最近选择的项目。如果是这样，只需在其现有分数中添加1.0。如果不是，则创建一个初始分数为1.0的新项目并将其添加到列表中。如果列表中没有更多空间（意味着它已经包含了您要显示的MRU项目的最大数量），则首先从列表中删除得分最低的项目（由于该项目总会位于列表的末尾）转到下一步）。
现在，按得分按降序对列表重新排序。 （最高分数应首先出现在MRU列表中）。


USAGE_WEIGHT因子确定将重要的“新近度”与“频率”（又称为使用次数）进行比较的方式。值为0.5将导致列表具有完全LRU行为（仅对最近度有影响），而值1.0将导致列表具有完全LRU行为（仅对使用计数有影响）。中间值（例如0.9）将导致列表具有LRU和LFU行为的混合，如下面的示例输出所示。

在下面的每种情况下，“值”都是字母，并按以下顺序添加：

A B C B A A D A C D A B D E C B A  

每次添加之后，我都会在引号（例如“ DBA”）中列出与当前MRU列表一起添加的字母。最大MRU大小为3。我还列出了列表的更详细表示形式，以 { Letter, Score }形式显示了每个项目的值（字母）和分数。

USAGE_WEIGHT = 1.0（完全LFU-仅使用计数）

  1. (Added A) "A"      [ { A, 1.0 } ]
  2. (Added B) "AB"     [ { A, 1.0 } { B, 1.0 } ]
  3. (Added C) "ABC"    [ { A, 1.0 } { B, 1.0 } { C, 1.0 } ]
  4. (Added B) "BAC"    [ { B, 2.0 } { A, 1.0 } { C, 1.0 } ]
  5. (Added A) "BAC"    [ { B, 2.0 } { A, 2.0 } { C, 1.0 } ]
  6. (Added A) "ABC"    [ { A, 3.0 } { B, 2.0 } { C, 1.0 } ]
  7. (Added D) "ABD"    [ { A, 3.0 } { B, 2.0 } { D, 1.0 } ]
  8. (Added A) "ABD"    [ { A, 4.0 } { B, 2.0 } { D, 1.0 } ]
  9. (Added C) "ABC"    [ { A, 4.0 } { B, 2.0 } { C, 1.0 } ]
 10. (Added D) "ABD"    [ { A, 4.0 } { B, 2.0 } { D, 1.0 } ]
 11. (Added A) "ABD"    [ { A, 5.0 } { B, 2.0 } { D, 1.0 } ]
 12. (Added B) "ABD"    [ { A, 5.0 } { B, 3.0 } { D, 1.0 } ]
 13. (Added D) "ABD"    [ { A, 5.0 } { B, 3.0 } { D, 2.0 } ]
 14. (Added E) "ABE"    [ { A, 5.0 } { B, 3.0 } { E, 1.0 } ]
 15. (Added C) "ABC"    [ { A, 5.0 } { B, 3.0 } { C, 1.0 } ]
 16. (Added B) "ABC"    [ { A, 5.0 } { B, 4.0 } { C, 1.0 } ]
 17. (Added A) "ABC"    [ { A, 6.0 } { B, 4.0 } { C, 1.0 } ]

USAGE_WEIGHT = 0.5（完全LRU-仅新近度很重要）

  1. (Added A) "A"      [ { A, 1.0 } ]
  2. (Added B) "BA"     [ { B, 1.0 } { A, 0.5 } ]
  3. (Added C) "CBA"    [ { C, 1.0 } { B, 0.5 } { A, 0.25 } ]
  4. (Added B) "BCA"    [ { B, 1.25 } { C, 0.5 } { A, 0.125 } ]
  5. (Added A) "ABC"    [ { A, 1.0625 } { B, 0.625 } { C, 0.25 } ]
  6. (Added A) "ABC"    [ { A, 1.5313 } { B, 0.3125 } { C, 0.125 } ]
  7. (Added D) "DAB"    [ { D, 1.0 } { A, 0.7656 } { B, 0.1563 } ]
  8. (Added A) "ADB"    [ { A, 1.3828 } { D, 0.5 } { B, 0.0781 } ]
  9. (Added C) "CAD"    [ { C, 1.0 } { A, 0.6914 } { D, 0.25 } ]
 10. (Added D) "DCA"    [ { D, 1.125 } { C, 0.5 } { A, 0.3457 } ]
 11. (Added A) "ADC"    [ { A, 1.1729 } { D, 0.5625 } { C, 0.25 } ]
 12. (Added B) "BAD"    [ { B, 1.0 } { A, 0.5864 } { D, 0.2813 } ]
 13. (Added D) "DBA"    [ { D, 1.1406 } { B, 0.5 } { A, 0.2932 } ]
 14. (Added E) "EDB"    [ { E, 1.0 } { D, 0.5703 } { B, 0.25 } ]
 15. (Added C) "CED"    [ { C, 1.0 } { E, 0.5 } { D, 0.2852 } ]
 16. (Added B) "BCE"    [ { B, 1.0 } { C, 0.5 } { E, 0.25 } ]
 17. (Added A) "ABC"    [ { A, 1.0 } { B, 0.5 } { C, 0.25 } ]

USAGE_WEIGHT = 0.9（LRFU-LRU和LFU的混合物）

  1. (Added A) "A"  [ { A, 1.0 } ]
  2. (Added B) "BA" [ { B, 1.0 } { A, 0.9 } ]
  3. (Added C) "CBA"    [ { C, 1.0 } { B, 0.9 } { A, 0.81 } ]
  4. (Added B) "BCA"    [ { B, 1.81 } { C, 0.9 } { A, 0.729 } ]
  5. (Added A) "ABC"    [ { A, 1.6561 } { B, 1.629 } { C, 0.81 } ]
  6. (Added A) "ABC"    [ { A, 2.4905 } { B, 1.4661 } { C, 0.729 } ]
  7. (Added D) "ABD"    [ { A, 2.2414 } { B, 1.3195 } { D, 1.0 } ]
  8. (Added A) "ABD"    [ { A, 3.0173 } { B, 1.1875 } { D, 0.9 } ]
  9. (Added C) "ABC"    [ { A, 2.7156 } { B, 1.0688 } { C, 1.0 } ]
 10. (Added D) "ADB"    [ { A, 2.444 } { D, 1.0 } { B, 0.9619 } ]
 11. (Added A) "ADB"    [ { A, 3.1996 } { D, 0.9 } { B, 0.8657 } ]
 12. (Added B) "ABD"    [ { A, 2.8796 } { B, 1.7791 } { D, 0.81 } ]
 13. (Added D) "ADB"    [ { A, 2.5917 } { D, 1.729 } { B, 1.6012 } ]
 14. (Added E) "ADE"    [ { A, 2.3325 } { D, 1.5561 } { E, 1.0 } ]
 15. (Added C) "ADC"    [ { A, 2.0993 } { D, 1.4005 } { C, 1.0 } ]
 16. (Added B) "ADB"    [ { A, 1.8893 } { D, 1.2604 } { B, 1.0 } ]
 17. (Added A) "ADB"    [ { A, 2.7004 } { D, 1.1344 } { B, 0.9 } ]

在第一个示例（USAGE_WEIGHT = 1.0）中，添加新项目时，现有项目的得分不会改变（这是因为我们在每一步上都乘以1.0）。这将导致每次使用后简单地将分数增加1.0，因此分数直接表示使用次数。请注意，项始终按使用量递减的顺序列出。

在第二个示例（USAGE_WEIGHT = 0.5）中，每次添加一个项目时，现有项目的得分都会减半（这是因为我们在每个步骤上都乘以0.5）。这导致属性，列表中的所有分数均低于最近添加的项目（得分为1.0），而且在第N步添加的项目总是比添加的项目总得分更高。 N之前的任何步骤，无论该项目被重新添加多少次。这正是产生LRU策略的属性。

最后，当（USAGE_WEIGHT = 0.9）时，我们可以看到两种策略是如何混合使用的。第三个示例看起来像LRU（即“新近度”很重要）。但是，随着某些项的使用次数开始增加，它们开始起作用并改变行为。这可以在步骤7中看到，其中LRU列出了“ DAB”，但是由于A和B的使用率较高，示例3中显示了“ ABD”。然后，示例3在几步中看起来更像是LFU，但有趣的是在步骤3 10.这是LRFU开始发光的地方。至此，A被添加了4次，而“ B”，“ C”和“ D”分别被添加了两次。 LRU显示“ DCA”是因为最近添加了“ D”和“ C”，但是它忽略了这样一个事实，即用户选择“ A”的可能性是“ D”或“ C”的两倍。 LFU显示“ ABD”是可以的，除了用户在选择“ B”之后两次选择“ D”之外，这表明“ D”的使用正在“升温”，因此比“ B”更有可能。 LRFU通过显示“ ADB”来正确处理它。当然，这全都是主观的，其他读者可能不同意这是一个更好的选择。毕竟，我们试图根据以前的历史预测用户的未来选择，因此没有完美的解决方案。但是，使用LRFU，您至少可以“调整” USAGE_WEIGHT参数，以找到给定情况下LRU与LFU的正确平衡。

实际上，对于某些应用程序，随着程序的进展以动态地更改USAGE_WEIGHT可能会更可取，以改进基于历史数据的预测。对于用户界面MRU列表，这可能没有任何意义，但对于预测大量或高频事件更有意义。

仅供参考，在本文讨论的LRFU算法中，分数称为“ CRF”。他们讨论的算法还存储了计算每个分数的“时间”（或步数）。通过存储分数和时间，可以仅更新要添加的商品以及一小部分商品的分数，而不是整个列表。此外，排序顺序由堆和链接列表数据结构的组合来维护，因此该算法比我在此描述的使用简单数组并在每次添加后对列表进行重新计算和重新排序的效率要高得多。但是此实现非常简单，易于理解，并且可以很好地用于用户界面MRU列表。

这是Java中朴素的LRFU列表的非常基本的实现。在性能方面可以做很多改进，但是足以证明LRFU的结果：

public static void main( String[] args ) {
    double[] weights = { 1.0, 0.5, 0.9 };
    for(double weight : weights) {
        System.out.println("USAGE_WEIGHT = " + weight);
        testMRU(weight);
        System.out.println();
    }
}

private static void testMRU(double weight) {
    PrintStream p = System.out;
    MRUList<String> list = new MRUList<>(3, weight);
    String[] lettersAdded = "A B C B A A D A C D A B D E C B A".split(" ");
    for(int i = 0; i < lettersAdded.length; i++) {
        String value  = lettersAdded[i];
        list.add(value);
        p.printf("%3s. (Added %s) \"", i, value);
        for(MRUItem<String> item : list.list)
            p.print(item.Value);
        p.print("\"\t[ ");
        for(MRUItem<String> item : list.list) {
            p.printf("{ %s, %.5s } ", item.Value, item.Score);
        }
        p.println("]");
    }
}

private static class MRUList<T> {
    public static final double SCORE_INIT = 1.0;

    private double usageWeight; // factor that balances LRU vs LFU
    private int maxSize; // maximum number of MRU items.
    public ArrayList<MRUItem<T>> list;

    public MRUList(int maxItemCount) { this(maxItemCount, 0.9); }
    public MRUList(int maxItemCount, double usageWeightFactor) {
        maxSize = maxItemCount;
        usageWeight = usageWeightFactor;
        list = new ArrayList<>(maxSize);
    }

    // Add an item each time the user chooses it.
    public void add(T value) {
        // Update the score of all existing items
        for(MRUItem<T> item : list)
            item.Score *= usageWeight; // age the items (this does not affect sort order)

        // Search for the item in the list.
        MRUItem<T> existing = find(value);
        if (existing==null) {
            existing = new MRUItem<>(value, SCORE_INIT);
            if (list.size()<maxSize) {
                // we have room -- add the item.
                list.add(existing);
            } else {
                // no more room -- replace last item.
                list.set(list.size() - 1, existing);
            }
        } else {
            // increment the score of the item if it already existed in the list.
            existing.Score += SCORE_INIT;
        }

        // Sort the items for display.
        // Collections.sort uses the Comparable interface of MRUItem.
        Collections.sort(list);
    }

    // Get a copy of the list of items, in the correct display order.
    public List<T> getItems() {
        ArrayList<T> copy = new ArrayList<>();
        for(MRUItem<T> item : list)
            copy.add(item.Value);
        return copy;
    }

    // return an item if it's Value is already present in the list.
    private MRUItem<T> find(T value) {
        for(MRUItem<T> item : list)
            if (Objects.equals(item.Value, value))
                return item;
        return null;
    }
}
private static class MRUItem<T> implements Comparable<MRUItem<T>> {
    public T Value;
    public double Score;
    public MRUItem(final T value, final double score) {
        Score = score;
        Value = value;
    }

    // Sorts by Score in descending order (due to - sign)
    @Override
    public int compareTo(final MRUItem<T> other) {
        return -Double.compare(Score, other.Score);
    }
}