Java中的矢量選項

我正在使用矢量對象。我的問題是從矢量中刪除是昂貴的操作（O（n^2））。什麼是Java中的矢量替換。在我的使用中，廣泛地發生添加和移除。Java中的矢量選項

我是C++的人不知道很多的Java

2011-04-12 CrazyC

您關於'remove'操作運行時間的信息是錯誤的。除此之外，使用'ArrayList'而不是'Vector'。 – 2011-04-12 11:12:09

ArrayList的添加和刪除行爲是什麼？ – CrazyC 2011-04-12 11:14:18

@ Saurabh01與'Vector'一樣 - 它本質上是一樣的，但沒有無用的同步。 'Vector'很大程度上已經過時，並已被'ArrayList'取代。正如我所說的，'remove'的運行時間是線性的，所以它比O（n^2）好得多。 – 2011-04-12 11:18:07

感謝大家對我的貢獻，幫助我解決了這個問題。我使用了一個循環隊列，這個隊列是在矢量的幫助下編寫的。

來源

2011-04-20 09:43:06 CrazyC

您可以使用ArrayList，而不是載體在Java中。

來源

2011-04-12 11:12:54 Ammu

那麼，不應該使用Vector類。 Java中有很多容器可用。其中很少：

ArrayList適合隨機訪問，但不適合插入或從列表中移除。

LinkedList對隨機訪問不好，但對於從容器中間迭代和添加/刪除元素來說是公平的。

來源

2011-04-12 11:13:39 StKiller

看看這篇文章：

http://www.javaworld.com/javaworld/javaqa/2001-06/03-qa-0622-vector.html

的LinkedList可以添加/刪除在O項（1）

來源

2011-04-12 11:14:31

謝謝。很有用。 – CrazyC 2011-04-12 11:21:49

首先，矢量去除時間複雜度爲O（n）不爲O（n^2）。如果你想要更高性能的類，你應該選擇LinkedList。它的時間複雜度是不變的。

來源

2011-04-12 11:16:50

我想，Vector using System.arrayCopy的複雜性是O（n^2） – CrazyC 2011-04-12 11:22:46

這不是真的，你是如何得到System.arraycopy是O（n^2）這樣的想法的？ – 2011-04-12 12:24:54

也許列表不是您的用例的理想數據結構 - 如果元素的排序不重要，您最好使用HashSet嗎？

來源

2011-04-12 11:17:24 tofarr

實際上，Vector和ArrayList之間的差異是Vector是同步的，而ArrayList不是。一般來說，你不需要同步，因此你會使用ArrayList（很像StringBuffer < - >StringBuilder）。

更換主要取決於你打算如何使用集合。

將對象添加到ArrayList的速度非常快，因爲如果需要更多空間，它通常會加倍，並且如果您事先知道尺寸要求，甚至更好。

從ArrayList中刪除的是O（n），但迭代和隨機訪問都很快。

如果您頻繁地添加或刪除操作，或者對列表進行迭代，則LinkedList就可以。

你甚至可以考慮使用LinkedHashMap，它允許快速訪問以及保留插入的順序。

來源

2011-04-12 11:20:30 Thomas

我正在使用它添加整數數據類型以及一些自定義對象。我也想保留插入順序。 – CrazyC 2011-04-12 11:25:02

我不知道大概的大小。 – CrazyC 2011-04-12 11:27:55

所以你有一個可以是任何類型的對象列表？嗯，這是一個危險的設計。你能展示一些代碼嗎？ – Thomas 2011-04-12 11:29:18

我認爲，使用System.arrayCopy載體，其複雜性爲O（n^2）

該Vector將使用System.arrayCopy移動元件這是正確的。然而System.arrayCopy()呼叫副本最多Vector.size()元素，因此是O(N)其中N是向量的大小。

因此O(N^2)對於單次插入/刪除不正確。

事實上，如果你想比O(N)插入和刪除更好，你將需要使用某種類型的鏈表類型與遊標抽象，允許插入和刪除，在「當前位置」。即使這樣，如果您可以按照正確的順序進行插入/刪除，那麼您只會比O(N)更好;即不是隨機順序。

FWIW，Java List API不提供這樣的遊標機制......至少因爲它使用起來很尷尬，而且在某些情況/實現中只有效。

來源

2011-04-12 11:33:11

Java中的矢量選項

回答

相關問題