jjzjj

Javascript:有效地将项目移入和移出固定大小的数组

coder 2024-07-24 原文

如果我想要一个固定大小的数组 N 以便缓存最近的 N 项，那么一旦限制 N 已达到，我必须在添加最新项的同时删除最旧的项。

注意:我不关心最新的项目是在数组的开头还是结尾，只要项目按照添加的顺序被删除即可。

最明显的方法是:

  • push() 和 shift()(以便 cache[0] 包含最旧的项目)，或者
  • unshift() 和 pop()(以便 cache[0] 包含最新的项目)

基本思路:

var cache = [], limit = 10000;

function cacheItem( item ) {

    // In case we want to do anything with the oldest item
    // before it's gone forever.
    var oldest = [];

    cache.push( item );

    // Use WHILE and >= instead of just IF in case the cache
    // was altered by more than one item at some point.
    while ( cache.length >= limit ) {
        oldest.push( cache.shift() );
    }

    return oldest;
}

但是，我已经阅读了有关 shift 和 unshift 的内存问题，因为它们改变了数组的开头并移动了其他所有内容，但不幸的是，必须使用其中一种方法才能做到这一点!

问题:

  1. 是否有其他方法可以提高性能？
  2. 如果我已经提到的两种方式是最好的，是否有我需要注意的具体优势/劣势？


结论

在对数据结构做了更多研究之后(我从来没有用其他语言编程过，所以如果它不是 Javascript 原生的，我可能没有听说过它!)并在多个浏览器中使用这两种语言进行了一系列基准测试小型和大型阵列以及小型和大量读/写，这是我发现的:

  • Bergi 提出的“循环缓冲区”方法无疑是迄今为止性能最好的方法(原因在答案和评论中有解释)，因此它已被接受为答案。然而，它并不那么直观，并且很难编写您自己的“额外”函数(因为您总是必须考虑 offset)。如果你打算使用这种方法，我推荐一个已经创建的方法，比如 this circular buffer on GitHub .
  • “pop/unpush”方法更直观，并且性能相当好，接受最极端的数字。
  • 可悲的是，'copyWithin' 方法的性能很糟糕(在多个浏览器中测试过)，会迅速造成 Not Acceptable 延迟。它也没有 IE 支持。就是这么简单的方法!我希望它能更好地工作。
  • “链表”方法，在Felix Kling的评论中提出, 实际上是一个非常好的选择。我最初无视它，因为它似乎有很多我不需要的额外东西，但令我惊讶的是......

我真正需要的是 Least Recently Used (LRU) Map (它使用双向链表)。现在，由于我没有在我的原始问题中指定我的附加要求，我仍然将 Bergi 的回答标记为该特定问题的最佳答案。但是，由于我需要知道某个值是否已存在于我的缓存中，如果存在，则将其标记为缓存中的最新项，因此我必须向循环缓冲区的 add() 添加额外的逻辑> 方法(主要是 indexOf())使它的效率并不比“pop/unpush”方法高多少。然而，LRUMap 在这些情况下的性能将其他两个都打败了!

总结一下:

  1. 链表 -- 大多数选项，同时仍保持出色的性能
  2. Circular Buffer -- 仅添加和获取的最佳性能
  3. Pop/Unpush -- 最直观和最简单
  4. copyWithin -- 当前性能糟糕，没有理由使用

最佳答案

If I have an array that caches the most recent of N items, once limit N is reached, I'll have to get rid of the oldest while adding the newest.

您不想在数组中到处复制内容，这每次都需要 O(n) 步。

相反，这是 ring buffer 的完美用例.只需保留列表“开始”和“结束”的偏移量，然后使用该偏移量访问您的缓冲区并对其长度取模。

var cache = new Array(10000);
cache.offset = 0;

function cacheItem(item) {
    cache[cache.offset++] = item;
    cache.offset %= cache.length;
}
function cacheGet(i) { // backwards, 0 is most recent
    return cache[(cache.offset - 1 - i + cache.length) % cache.length];
}

关于Javascript:有效地将项目移入和移出固定大小的数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48060887/

Javascript有效codecacheliarrayscaching

有关Javascript:有效地将项目移入和移出固定大小的数组的更多相关文章

  1. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  4. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  5. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  6. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  7. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  8. ruby-on-rails - 项目升级后 Pow 不会更改 ruby​​ 版本 - 2

    我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby​​版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby​​版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘

  9. ruby-on-rails - 新 Rails 项目 : 'bundle install' can't install rails in gemfile - 2

    我已经像这样安装了一个新的Rails项目:$railsnewsite它执行并到达:bundleinstall但是当它似乎尝试安装依赖项时我得到了这个错误Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcheckingforlibkern/OSAtomic.h...yescreatingMakefilemake"DESTDIR="cleanmake"DESTDIR="

  10. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

随机推荐