排序数组的最快搜索方法是什么？
回答另一个问题 ，我编写了下面的程序来比较排序数组中的不同搜索方法。 基本上我比较了插值搜索和二分搜索的两种实现。 我通过计算不同变体所花费的周期（使用相同的数据集）来比较性能。
但是我确信有一些方法可以优化这些function，使它们更快。 有没有人对如何更快地使这个搜索function有任何想法？ 使用C或C ++的解决方案是可以接受的，但我需要它来处理具有100000个元素的数组。
#include #include #include #include #include static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); return x; } int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int64_t low = 0; int64_t high = len - 1; int64_t mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l = toFind) { mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(hl)); int m = sortedArray[mid]; if (m toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int interpolationSearch2(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l = toFind) { mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(hl)); int m = sortedArray[mid]; if (m toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int binarySearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l = toFind) { mid = (low + high)/2; int m = sortedArray[mid]; if (m toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int order(const void *p1, const void *p2) { return *(int*)p1-*(int*)p2; } int main(void) { int i = 0, j = 0, size = 100000, trials = 10000; int searched[trials]; srand(-time(0)); for (j=0; j 10){ int arr[size]; for (i=0; i<size; i++) { arr[i] = rand()%size; } qsort(arr,size,sizeof(int),order); unsigned long long totalcycles_bs = 0; unsigned long long totalcycles_is_64 = 0; unsigned long long totalcycles_is_float = 0; unsigned long long totalcycles_new = 0; int res_bs, res_is_64, res_is_float, res_new; for (j=0; j>= 1; } } 如果您可以控制数据的内存中布局，则可能需要查看Judy数组。
或者在那里提出一个更简单的想法：二元搜索总是将搜索空间减少一半。 可以通过插值找到最佳切割点（切割点不应该是预期密钥的位置，而是最小化搜索空间对下一步骤的统计期望的点）。 这最大限度地减少了步骤的数量，但并非所有步骤都具有相同的成本。 如果可以维持位置，则分层存储器允许在单个测试的同时执行多个测试。 由于二进制搜索的前M个步骤仅触及最多2 ** M个唯一元素，因此将这些存储在一起可以更好地减少每个高速缓存行获取的搜索空间（不是每次比较），这在现实世界中具有更高的性能。
n-ary树在此基础上工作，然后Judy数组添加一些不太重要的优化。
底线：即使“随机存取存储器”（RAM）在顺序访问时比随机访问更快。 搜索算法应该利用这一事实。
基于Win32 Core2 Quad Q6600，gcc v4.3 msys进行基准测试。 用g ++ -O3编译，没什么特别的。
观察 – 断言，定时和循环开销约为40％，因此下面列出的任何增益应除以0.6，以获得被测算法的实际改进。
答案简单：
-
在我的机器上，用int替换int64_t为“低”，插值搜索中的“高”和“中”使速度提高20％到40％。 这是我能找到的最简单的方法。 在我的机器上每次查找大约需要150个周期（arrays大小为100000）。 这与缓存未命中的周期数大致相同。 因此，在实际应用中，照顾缓存可能是最重要的因素。
-
用“>> 1”替换binarySearch的“/ 2”可使速度提高4％。
-
在包含与“arr”相同的数据的向量上使用STL的binary_search算法，与手动编码的binarySearch大致相同。 虽然在较小的“尺寸”上，STL要慢得多 – 大约40％。
我有一个过于复杂的解决方案，需要专门的排序function。 排序比快速排序稍慢，但我的所有测试都显示搜索function比二进制或插值搜索快得多。 在我发现这个名字已经被采用之前，我把它称为回归排序，但是没有想到一个新名称（想法？）。
有三个文件可供演示。
回归排序/搜索代码：
#include #include #include #include "limits.h" void insertionSort(int array[], int length) { int key, j; for(int i = 1; i < length; i++) { key = array[i]; j = i - 1; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; --j; } array[j + 1] = key; } } class RegressionTable { public: RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs); RegressionTable(int arr[], int s); void sort(void); int find(int key); void printTable(void); void showSize(void); private: void createTable(void); inline unsigned int resolve(int n); int * array; int * table; int * tableSize; int size; int lowerBound; int upperBound; int divisions; int divisionSize; int newSize; double multiplier; }; RegressionTable::RegressionTable(int arr[], int s) { array = arr; size = s; multiplier = 1.35; divisions = sqrt(size); upperBound = INT_MIN; lowerBound = INT_MAX; for (int i = 0; i < size; ++i) { if (array[i] > upperBound) upperBound = array[i]; if (array[i] < lowerBound) lowerBound = array[i]; } createTable(); } RegressionTable::RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs) { array = arr; size = s; lowerBound = lower; upperBound = upper; multiplier = mult; divisions = divs; createTable(); } void RegressionTable::showSize(void) { int bytes = sizeof(*this); bytes = bytes + sizeof(int) * 2 * (divisions + 1); } void RegressionTable::createTable(void) { divisionSize = size / divisions; newSize = multiplier * double(size); table = new int[divisions + 1]; tableSize = new int[divisions + 1]; for (int i = 0; i < divisions; ++i) { table[i] = 0; tableSize[i] = 0; } for (int i = 0; i < size; ++i) { ++table[((array[i] - lowerBound) / divisionSize) + 1]; } for (int i = 1; i <= divisions; ++i) { table[i] += table[i - 1]; } table[0] = 0; for (int i = 0; i < divisions; ++i) { tableSize[i] = table[i + 1] - table[i]; } } int RegressionTable::find(int key) { double temp = multiplier; multiplier = 1; int minIndex = table[(key - lowerBound) / divisionSize]; int maxIndex = minIndex + tableSize[key / divisionSize]; int guess = resolve(key); double t; while (array[guess] != key) { // uncomment this line if you want to see where it is searching. //cout << "Regression Guessing " << guess << ", not there." << endl; if (array[guess] < key) { minIndex = guess + 1; } if (array[guess] > key) { maxIndex = guess - 1; } if (array[minIndex] > key || array[maxIndex] < key) { return -1; } t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]); guess = minIndex + t * (maxIndex - minIndex); } multiplier = temp; return guess; } inline unsigned int RegressionTable::resolve(int n) { float temp; int subDomain = (n - lowerBound) / divisionSize; temp = n % divisionSize; temp /= divisionSize; temp *= tableSize[subDomain]; temp += table[subDomain]; temp *= multiplier; return (unsigned int)temp; } void RegressionTable::sort(void) { int * out = new int[int(size * multiplier)]; bool * used = new bool[int(size * multiplier)]; int higher, lower; bool placed; for (int i = 0; i < size; ++i) { /* Figure out where to put the darn thing */ higher = resolve(array[i]); lower = higher - 1; if (higher > newSize) { higher = size; lower = size - 1; } else if (lower < 0) { higher = 0; lower = 0; } placed = false; while (!placed) { if (higher < size && !used[higher]) { out[higher] = array[i]; used[higher] = true; placed = true; } else if (lower >= 0 && !used[lower]) { out[lower] = array[i]; used[lower] = true; placed = true; } --lower; ++higher; } } int index = 0; for (int i = 0; i < size * multiplier; ++i) { if (used[i]) { array[index] = out[i]; ++index; } } insertionSort(array, size); }
然后是常规搜索function：
#include using namespace std; int binarySearch(int array[], int start, int end, int key) { // Determine the search point. int searchPos = (start + end) / 2; // If we crossed over our bounds or met in the middle, then it is not here. if (start >= end) return -1; // Search the bottom half of the array if the query is smaller. if (array[searchPos] > key) return binarySearch (array, start, searchPos - 1, key); // Search the top half of the array if the query is larger. if (array[searchPos] < key) return binarySearch (array, searchPos + 1, end, key); // If we found it then we are done. if (array[searchPos] == key) return searchPos; } int binarySearch(int array[], int size, int key) { return binarySearch(array, 0, size - 1, key); } int interpolationSearch(int array[], int size, int key) { int guess = 0; double t; int minIndex = 0; int maxIndex = size - 1; while (array[guess] != key) { t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]); guess = minIndex + t * (maxIndex - minIndex); if (array[guess] < key) { minIndex = guess + 1; } if (array[guess] > key) { maxIndex = guess - 1; } if (array[minIndex] > key || array[maxIndex] < key) { return -1; } } return guess; }
然后我写了一个简单的主要来测试不同种类。
#include #include #include #include #include "regression.h" #include "search.h" using namespace std; void randomizeArray(int array[], int size) { for (int i = 0; i < size; ++i) { array[i] = rand() % size; } } int main(int argc, char * argv[]) { int size = 100000; string arg; if (argc > 1) { arg = argv[1]; size = atoi(arg.c_str()); } srand(time(NULL)); int * array; cout << "Creating Array Of Size " << size << "...\n"; array = new int[size]; randomizeArray(array, size); cout << "Sorting Array...\n"; RegressionTable t(array, size, 0, size*2.5, 1.5, size); //RegressionTable t(array, size); t.sort(); int trials = 10000000; int start; cout << "Binary Search...\n"; start = clock(); for (int i = 0; i < trials; ++i) { binarySearch(array, size, i % size); } cout << clock() - start << endl; cout << "Interpolation Search...\n"; start = clock(); for (int i = 0; i < trials; ++i) { interpolationSearch(array, size, i % size); } cout << clock() - start << endl; cout << "Regression Search...\n"; start = clock(); for (int i = 0; i < trials; ++i) { t.find(i % size); } cout << clock() - start << endl; return 0; }
试一试，告诉我你是否更快。 这是非常复杂的，所以如果你不知道自己在做什么，那么打破它真的很容易。 修改它时要小心。
我在ubuntu上用g ++编译了main。
除非您的数据已知具有特殊属性，否则纯插值搜索可能会占用线性时间。 如果您期望插值可以帮助处理大多数数据，但是在病理数据的情况下不希望它受到伤害，我会使用插值猜测和中点的（可能加权的）平均值，确保运行时间的对数界限。
解决这个问题的一种方法是使用空间与时间的权衡。 有许多方法可以做。 最简单的方法是简单地创建一个数组，其中max size是排序数组的最大值。 使用索引将每个位置初始化为sortedArray。 然后搜索将只是O（1）。
但是，以下版本可能更加真实，可能在现实世界中有用。 它使用在第一次调用时初始化的“辅助”结构。 它将搜索空间向下映射到较小的空间，除以我从空中拉出的数字而不需要太多测试。 它将sortedArray中一组值的下限索引存储到辅助映射中。 实际搜索按所选除数除以toFind数，并提取sortedArray的缩小边界以进行常规二分搜索。
例如，如果排序值的范围为1到1000且除数为100，则查找数组可能包含10个“节”。 要搜索值250，它将除以100以产生整数索引位置250/100 = 2。 map[2]将包含值为200或更大的sortedArray索引。 map[3]将具有值300和更大的索引位置，从而为正常二进制搜索提供更小的边界位置。 然后，函数的其余部分是二进制搜索函数的精确副本。
辅助映射的初始化可能通过使用二进制搜索来填充位置而不是简单的扫描更有效，但它是一次性成本，所以我没有打扰测试。 这种机制适用于均匀分布的给定测试数。 如上所述，如果分布不均匀则不会那么好。 我认为这种方法也可以用于浮点搜索值。 但是，将其外推到通用搜索键可能会更难。 例如，我不确定字符数据键的方法是什么。 它需要某种O（1）lookup / hash映射到特定的数组位置以找到索引边界。 目前我不清楚这个function是什么，或者它是否存在。
我很快就在以下实现中完成了辅助映射的设置。 它不漂亮，我不是100％肯定它在所有情况下都是正确的，但它确实显示了这个想法。 我用调试测试运行它来比较你现有的binarySearch函数的结果，以确定它是否正常工作。
以下是示例数字：
100000 * 10000 : cycles binary search = 10197811 100000 * 10000 : cycles interpolation uint64_t = 9007939 100000 * 10000 : cycles interpolation float = 8386879 100000 * 10000 : cycles binary w/helper = 6462534
这是快速而肮脏的实现：
#define REDUCTION 100 // pulled out of the air typedef struct { int init; // have we initialized it? int numSections; int *map; int divisor; } binhelp; int binarySearchHelp( binhelp *phelp, int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low; int high; int mid; if ( !phelp->init && len > REDUCTION ) { int i; int numSections = len / REDUCTION; int divisor = (( sortedArray[len-1] - 1 ) / numSections ) + 1; int threshold; int arrayPos; phelp->init = 1; phelp->divisor = divisor; phelp->numSections = numSections; phelp->map = (int*)malloc((numSections+2) * sizeof(int)); phelp->map[0] = 0; phelp->map[numSections+1] = len-1; arrayPos = 0; // Scan through the array and set up the mapping positions. Simple linear // scan but it is a one-time cost. for ( i = 1; i <= numSections; i++ ) { threshold = i * divisor; while ( arrayPos < len && sortedArray[arrayPos] < threshold ) arrayPos++; if ( arrayPos < len ) phelp->map[i] = arrayPos; else // kludge to take care of aliasing phelp->map[i] = len - 1; } } if ( phelp->init ) { int section = toFind / phelp->divisor; if ( section > phelp->numSections ) // it is bigger than all values return -1; low = phelp->map[section]; if ( section == phelp->numSections ) high = len - 1; else high = phelp->map[section+1]; } else { // use normal start points low = 0; high = len - 1; } // the following is a direct copy of the Kriss' binarySearch int l = sortedArray[low]; int h = sortedArray[high]; while (l <= toFind && h >= toFind) { mid = (low + high)/2; int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found }
需要初始化辅助结构（并释放内存）：
help.init = 0; unsigned long long totalcycles4 = 0; ... make the calls same as for the other ones but pass the structure ... binarySearchHelp(&help, arr,searched[j],length); if ( help.init ) free( help.map ); help.init = 0;
首先查看数据以及通过一般方法通过数据特定方法是否可以获得大的收益。
对于大型静态排序数据集，您可以根据您愿意使用的内存量创建一个额外的索引来提供部分信息。 例如，我们创建一个256×256二维范围数组，我们用相应高阶字节的元素搜索数组中的起始位置和结束位置填充。 当我们来搜索时，我们然后使用键上的高位字节来找到我们需要搜索的数组的范围/子集。 如果我们对100,000个元素O（log2（n））的二进制搜索进行了~20次比较，那么现在我们已经将16个元素或者O（log2（n / 15））降低到~4个comarisons。 这里的内存成本约为512k
另一种方法，再次适用于变化不大的数据，是将数据分成常用物品和很少寻求的物品的数组。 例如，如果您将现有搜索保留在长时间测试期间运行大量真实案例，并记录所搜索项目的详细信息，您可能会发现分布非常不均匀，即某些值是比其他人更经常地寻求。 如果是这种情况，请将数组分成更小的常用值和更大的剩余数组，然后先搜索较小的数组。 如果数据是正确的（如果！），您通常可以在没有内存成本的情况下实现与第一个解决方案大致相似的改进。
还有许多其他数据特定的优化，其得分远远好于尝试改进经过试验，测试和更广泛使用的通用解决方案。
在问题关闭之前发布我当前的版本（希望我能够在以后增强它）。 现在它比其他所有版本都要糟糕（如果有人理解为什么我对循环结束的更改有这种影响，欢迎提出意见）。
int newSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l < toFind && h > toFind) { mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(hl)); int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (l == toFind) return low; else if (h == toFind) return high; else return -1; // Not found }
可以改进用于比较的二进制搜索的实现。 关键的想法是最初“规范化”范围，以便目标始终>最小值并且<第一步之后的最大值。 这增加了终止增量大小。 它还具有特殊套管目标的效果，该目标小于排序数组的第一个元素或大于排序数组的最后一个元素。 预计搜索时间将缩短约15％。 以下是C ++中代码的外观。
int binarySearch(int * &array, int target, int min, int max) { // binarySearch // normalize min and max so that we know the target is > min and < max if (target <= array[min]) // if min not normalized { // target <= array[min] if (target == array[min]) return min; return -1; } // end target <= array[min] // min is now normalized if (target >= array[max]) // if max not normalized { // target >= array[max] if (target == array[max]) return max; return -1; } // end target >= array[max] // max is now normalized while (min + 1 < max) { // delta >=2 int tempi = min + ((max - min) >> 1); // point to index approximately in the middle between min and max int atempi = array[tempi]; // just in case the compiler does not optimize this if (atempi > target)max = tempi; // if the target is smaller, we can decrease max and it is still normalized else if (atempi < target)min = tempi; // the target is bigger, so we can increase min and it is still normalized else return tempi; // if we found the target, return with the index // Note that it is important that this test for equality is last because it rarely occurs. } // end delta >=2 return -1; // nothing in between normalized min and max } // end binarySearch