Хранение блока чисел в эффективной структуре данных
У меня есть блоки чисел, например, - 1 - 4, 5 - 15, 16 - 21, 22 - 34.... У меня есть примерно 600 000 таких блоков. Диапазон чисел, которые падают в каждом блоке, варьируется. Я должен сохранить эти блоки в подходящей структуре данных так, чтобы поиски для числа были максимально быстро.
Таким образом, мой вопрос - то, что является подходящей структурой данных и механизмом сортировки для этого типа проблемы.
Заранее спасибо
5 ответов
Если сегменты смежные и непересекающиеся, как в вашем примере, вам нужно сохранить в векторе только левую границу каждого сегмента (т.е. 1, 5 , 16, 22) плюс в качестве последнего элемента первое число, которое не попадает ни в одну корзину (35). (Я предполагаю, конечно, что вы говорите о целых числах.)
Сохраняйте вектор отсортированным.
Вы можете искать в корзине за O (log n), с kind- бинарного поиска. Чтобы найти, к какому сегменту принадлежит число x, просто выберите единственный индекс i, такой что vector [i] <= x РЕДАКТИРОВАТЬ. Вот что я имею в виду: #include <stdio.h>
// ~ Binary search. Should be O(log n)
int findBucket(int aNumber, int *leftBounds, int left, int right)
{
int middle;
if(aNumber < leftBounds[left] || leftBounds[right] <= aNumber) // cannot find
return -1;
if(left + 1 == right) // found
return left;
middle = left + (right - left)/2;
if( leftBounds[left] <= aNumber && aNumber < leftBounds[middle] )
return findBucket(aNumber, leftBounds, left, middle);
else
return findBucket(aNumber, leftBounds, middle, right);
}
#define NBUCKETS 12
int main(void)
{
int leftBounds[NBUCKETS+1] = {1, 4, 7, 15, 32, 36, 44, 55, 67, 68, 79, 99, 101};
// The buckets are 1-3, 4-6, 7-14, 15-31, ...
int aNumber;
for(aNumber = -3; aNumber < 103; aNumber++)
{
int index = findBucket(aNumber, leftBounds, 0, NBUCKETS);
if(index < 0)
printf("%d: Bucket not found\n", aNumber);
else
printf("%d belongs to the bucket %d-%d\n", aNumber, leftBounds[index], leftBounds[index+1]-1);
}
return 0;
}
+1 к идее бинарного поиска. Это просто и дает хорошую производительность для 600000 ведер. При этом, если он недостаточно хорош, вы можете создать массив с элементами MAX BUCKET VALUE - MIN BUCKET VALUE = RANGE, и каждый элемент в этом массиве будет ссылаться на соответствующий сегмент. Затем вы получаете поиск за гарантированное постоянное [O (1)] время за счет использования огромного объема памяти.
Если A) вероятность доступа к сегментам не одинакова и B) вы знали / могли вычислить, насколько вероятно, что данный набор сегментов будет доступен, вы, вероятно, могли бы объединить эти два подхода для создания своего рода кеша. Например, предположим, что к сегменту {0, 3} постоянно обращались, как и к {7, 13}, тогда вы можете создать массив CACHE. . .
int cache_low_value = 0;
int cache_hi_value = 13;
CACHE [0] = BUCKET_1
CACHE [1] = BUCKET_1
...
CACHE [6] = BUCKET_2
CACHE [7] = BUCKET_3
CACHE [8] = BUCKET_3
...
CACHE [13] = BUCKET_3
. . . который позволит вам найти сегмент за O (1) время, предполагая, что значение, которое вы пытаетесь связать с сегментом, находится между cache_low_value и cache_hi_value (если Y <= cache_hi_value && Y> = cache_low_value; тогда BUCKET = CACHE [ Y]). С другой стороны, этот подход не будет использовать всю память на вашем компьютере; с другой стороны, он добавит эквивалент одной или двух дополнительных операций к вашему bsearch в случае, если вы не можете найти свою пару номер / сегмент в кеше (поскольку вам нужно было сначала проверить кеш).
Простой способ сохранить и отсортировать их в C ++ - использовать пару отсортированных массивов, которые представляют нижнюю и верхнюю границы каждой корзины. Затем вы можете использовать int bucket_index = std :: distance (lower_bounds.begin (), std :: lower_bound (lower_bounds, value)) , чтобы найти сегмент, с которым будет соответствовать значение, и if (upper_bounds [bucket_index]> = value) , bucket_index - это то, что вам нужно.
Вы можете заменить это одной структурой, содержащей ведро, но принцип останется тем же.
Если я правильно вас понял, у вас есть список ведер, и вы хотите, задав произвольное целое число, узнать, в какое ведро оно попадет.
Предполагая, что ни один из диапазонов ведер не пересекается, я думаю, что вы могли бы реализовать это в дереве двоичного поиска. Это сделает поиск возможным за O(logn) (когда n=количество ведер).
Сделать это будет просто, достаточно определить левую ветвь как меньшую, чем нижний конец ведра, а правую - как большую, чем правый конец. Таким образом, в вашем примере мы получили бы дерево следующего вида:
16-21
/ \
5-15 22-34
/
1-4
Чтобы найти, скажем, 7, достаточно проверить корень. Меньше 16? Да, идем налево. Меньше 5? Нет. Больше 15? Нет, вы закончили.
Вы просто должны быть осторожны, чтобы сбалансировать ваше дерево (или использовать самобалансирующееся дерево), чтобы снизить производительность в худшем случае. это действительно важно, если ваши входные данные (список ведер) уже отсортированы.
Вероятно, вам понадобится какое-то отсортированное дерево, например, B-дерево, B+-дерево или дерево двоичного поиска.