树形VS数组列表 - 性能比较和放大器;资源的同时迭代/添加/编辑值 [英] treemap vs arraylist - perfomance & resources while iterating/adding/editing values

问题描述

说到性能和资源。

哪一个是速度更快，需要更少的资源，当添加和编辑值，ArrayList的或TreeMap的？

还是有可以击败这两个任何类型的数据？ （它必须能够以某种方式使数据排序）

解决方案

取决于你所需要的东西。

如果我们谈论的排序的数据，因为的ArrayList 是一个列表/数组，如果是排序，你可以得到一个值在 O（log n）的速度。要插入，虽然，它是 O（N），因为你可能已经插入一个新元素时移动整个数组。

的 TreeMap的数据结构实现为红黑树，这既插入时间和搜索时间 O（log n）的。

所以，概括地说：

 数据结构插入速度搜索速度
ArrayList的（排序）为O（n）O（log n）的
TreeMap的O（log n）的O（log n）的
 

我肯定会使用 TreeMap的去。它有它的一切准备就绪，现在（你必须实现的一些$ C $的Ç自己，使的ArrayList 作品）。<额外奖金/ p>

注意：结果
如果你没有得到的 O（N）（叫大哦）符号，把它作为所需的量秒的公式时，该结构具有 N 元素。所以，如果你有一个的ArrayList 1000元（ N = 1000 ），它会采取 3 秒（日志1000 = 3 ）找到一个项目出现。这将需要千秒来，虽然插入一个新元素。

的 TreeMap的，在另一方面，将采取的 3 秒到两个搜索和插入。

Talking about performance and resources.

Which one is faster and needs less resources when adding and editing values, ArrayList or TreeMap?

Or is there any type of data that can beat these two? (it has to be able to somehow make the data sorted)

解决方案

Depends on what you need.

If we are talking about sorted data, as the ArrayList is a list/array, if it is sorted, you could get a value in O(log n) speed. To insert, though, it is O(n), because you potentially have to move the whole array when inserting a new element.

The TreeMap data structure is implemented as a red-black tree, which both the insertion time and search time are O(log n).

So, in a nutshell:

Data Structure         Insertion Speed    Search Speed
ArrayList (sorted)     O(n)               O(log n)
TreeMap                O(log n)           O(log n)

I'd definitely go with a TreeMap. It has the additional bonus of having it all ready to go right now (you'd have to implement some of the code yourself to make the ArrayList work).

Note:
If you don't get the O(n) (called big-Oh) notation, think of it as a formula for the amount seconds needed when the structure has n elements. So, if you had an ArrayList with 1000 elements (n=1000), it'd take 3 seconds (log 1000 = 3) to find an item there. It would take 1000 seconds to insert a new element though.

The TreeMap, on the other hand, would take 3 seconds to both search and insert.

这篇关于树形VS数组列表 - 性能比较和放大器;资源的同时迭代/添加/编辑值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！