在桶中查找數字的最快方法是什麼？

假設每個存儲桶有一個對象表示5個存儲桶，那麼使用Java 8查找給定數量屬於哪個存儲桶的最快方法是什麼？在桶中查找數字的最快方法是什麼？

對於例如：

List <Bucket> listOfBuckets = new ArrayList<>();

並且每個桶對象具有以下屬性

"Buckets": [{ 
    "bucketName":"bucket1", 
    "lowerBound":0, 
    "upperBound":10 
}, { 
    "bucketName":"bucket2", 
    "lowerBound":11, 
    "upperBound":20 
}, { 
    "bucketName":"bucket3", 
    "lowerBound":21, 
    "upperBound":30 
}]

爲每個在{2,15,18,14,22}，找到相應的桶。

雖然有一種方法是循環遍歷每個數字的列表，但如果您正在檢查存儲區中的大量數字列表，則會變成開銷。

來源

2015-10-14 wishwas

讓我們稍微閱讀一下：https：//en.wikipedia.org/wiki/Category:Search_algorithms選擇一個，併爲之努力！ –

存儲桶是否已分類？ –

存儲桶未排序。 – wishwas

只是爲了記錄在案，Java提供了廣泛的Map實現 （例如HashMap）在內部使用桶。 HashMap使用java hashCode在內部將它們排列在桶中。或者還有其他的地圖與其他屬性（LinkedHashMap，ConcurrentHashMap，...）

甚至有不需要的關鍵精確匹配標準的Java地圖。他們實現了NavigableMap接口。（例如，一個TreeMap）

或者，（例如爲了教育目的），如果你想從頭開始，我會使用二進制搜索算法或索引。您可以申請"Bisection method"或"Binary search algorithm"。（另一方面，簡單的迭代被稱爲"Linear search algorithm"）。 二元搜索比線性搜索更有效率，特別是對於大型集合。

二分法搜索假定您的元素很好地排序。然後你開始嘗試中心元素（index = length/2）。如果您的索引包含正確的桶，那麼您可以立即退出。如果不是，則以左側或右側的索引爲中心。重複，直到找到它。

在代碼：

if (bucket[index].startId > requiredId) index = index + (length-index)/2; 
else if (bucket[index].stopId < requiredId) index = index - (length-index)/2; 
else return bucket[index];

圖：下圖顯示該算法如何用於搜索號碼的列表數7：

或者（或者另外），您可以在其上添加第二個（或第三個）存儲桶（比如索引）。（這也是how some database indexes work）。您的結構可以是這個樣子：

   bucket[1-70] 
      /  \ 
      bucket[1-25] bucket[25-70] 
     /   \   ... 
     bucket[1-15] bucket[15-25] 
      ...    ...

編輯：

在您的收藏不排序的時刻。如果你打算編寫自己的算法，那麼我會先解決它。您只需將ArrayList替換爲TreeSet即可。 A TreeSet已經在您每次添加元素時對元素進行排序。但是有一個要求：你的Bucket類需要實現Comparable接口和equals方法。

來源

2015-10-14 06:37:03 bvdb

如果桶下面的模式，如上面的例子中，你可以寫如下的實用工具方法：

private int getBucketIndex(int number) { 
    if(number between 0-10) return 0; 
    if(number between 11-20) return 1; 
    /*etc*/ 
} 

public Bucket getBucket(int number) { 
    return list.get(getBucketIndex(number)); 
}

來源

2015-10-14 06:31:13 user2350659

你想使用Java 8 特別爲此？

list.stream() 
    .map(n -> listOfBuckets.stream() 
          // Get rid of non-fitting buckets 
          .filter(b -> n >= b.lowerBound && n <= b.upperBound) 
          // Take the first fitting bucket found 
          .findFirst() 
          // No matching bucket? Throws NoSuchElementException 
          .get()) 
    .collect(Collectors.toList())

注意，你必須遍歷列表不管是什麼，所以鬥搜索將至少由O（n）爲界。因爲桶的列表是常量（5），所以這個搜索是O（5n），這意味着無論如何，執行時間都是線性增長的。

如果你有一個可變數量的桶，比如m，比一個線性搜索是O（m）並且搜索是O（n * m）或者O（這意味着執行時間隨着越來越多的桶而呈拋物線式增長。在這一點上，你應該考慮一個像樹一樣便宜的數據結構。這將使右桶的搜索時間爲O（log m），總搜索將變爲O（n log m）或對數增長，這比拋物線增長要好得多。

來源

2015-10-14 07:37:33 sh0rug0ru

在桶中查找數字的最快方法是什麼？

回答

相關問題