Как найти элемент в связанном списке блоков (содержащий n элементов) как можно быстрее? - PullRequest
Новая
       43

Как найти элемент в связанном списке блоков (содержащий n элементов) как можно быстрее?

0 голосов
/ 01 декабря 2010

Моя структура данных представляет собой связанный список блоков. Блок содержит 31 элемент по 4 байта и один 4 байтовый указатель на следующий блок или NULL (в сумме 128 байтов на блок). Я добавляю элементы время от времени. Если последний блок заполнен, я добавляю другой блок с помощью указателя.

Одна из целей состоит в том, чтобы использовать как можно меньше памяти (= блоков) и не иметь свободного пространства между двумя элементами в блоке.

Эта настройка исправлена. Весь код выполняется на 32-битном процессоре ARM Cortex-A8 с конвейером NEON.

Вопрос: Как найти конкретный элемент в этой структуре данных как можно быстрее?

Подход (прямо сейчас): Я использую отсортированные блоки и бинарный поиск для проверки элемента (9-битный из 4-х байтов является критерием поиска). Если нужного элемента нет в текущем блоке, я перехожу к следующему блоку. Если элемент находится не в последнем блоке, а последний блок еще не заполнен, я использую результат двоичного поиска для вставки нового элемента (при необходимости я делаю пробел, используя memmove внутри этого блока). При этом все блоки всегда сортируются.

У вас есть идея сделать это быстрее? Вот как я ищу прямо сейчас: (q-> getPosition () - встроенная функция, которая просто извлекает 9-битную позицию из элемента через "& bitmask") 

do
{
    // binary search algorithm (bsearch)
    // from http://www.google.com/codesearch/
    // p?hl=en#qoCVjtE_vOw/gcc4/trunk/gcc-
    // 4.4.3/libiberty/bsearch.c&q=bsearch&sa=N&cd=2&ct=rc

    base = &(block->points[0]);

    if (block->next == NULL)
    {
        pointsInBlock = pointsInLastBlock;
        stop = true;
    }
    else
    {
        block = block->next;
    }

    for (lim = pointsInBlock; lim != 0; lim >>= 1)
    {
        q = base + (lim >> 1);

        cmp = quantizedPosition - q->getPosition();

        if (cmp > 0)
        {
            // quantizedPosition > q: move right
            base = q + 1;
            lim--;
        }
        else if (cmp == 0)
        {
            // We found the QuantPoint
            *outQuantPoint = q;
            return true;
        }
        // else move left
    }
}
while (!stop);

Ответы [ 3 ]

2 голосов
/ 01 декабря 2010

Поскольку большая часть времени затрачивается на поиск внутри блока, это должно быть как можно быстрее.Поскольку количество элементов фиксировано, вы можете полностью развернуть этот цикл, например: 

if (key < a[16]){
  if (key < a[8]){
    ...
  }
  else { // key >= a[8] && key < a[16]
    ...
  }
}
else { // key >= a[16]
  if (key < a[24]){
    ...
  }
  else { // key >= a[24]
    ...
  }
}

Изучите сгенерированный язык ассемблера и пошагово его в отладчике, чтобы убедиться, что компилятор дает вам хороший код.

Возможно, вы захотите написать небольшую программу для распечатки приведенного выше кода, так как это будет сложно написать вручную, или, возможно, сгенерировать ее с помощью макросов.9-битный критерий поиска.В этом случае просто предварительно выделите массив из 512 4-байтовых слов и индексируйте его напрямую.Это самый быстрый и наименьший код.

ТАКЖЕ ДОБАВЛЕНО: Если вам нужно сохранить структуру блоков, есть еще один способ выполнить развернутый бинарный поиск.Это метод Джона Бентли: 

i = 0;
if (key >= a[i+16]) i += 16;
if (key >= a[i+ 8]) i +=  8;
if (key >= a[i+ 4]) i +=  4;
if (key >= a[i+ 2]) i +=  2;
if (i < 30 && key >= a[i+ 1]) i +=  1; // this excludes 31
if (key == a[i]) // then key is found

Это медленнее, чем дерево if, описанное выше, из-за манипулирования i, но может быть существенно меньше кода.

1 голос
/ 01 декабря 2010

если этот критерий поиска для элемента является фиксированным, вам лучше переместить поиск в отдельную структуру индекса, поскольку максимальное количество элементов, которые вы различаете по критерию поиска, составляет всего 2 ^ 9 = 512 индексов, поэтому максимальное размер поискового индекса будет (2 + 4) * 512 = 3072, но вы можете использовать другой, кроме статического, если вам нужно, сэкономив немного памяти. Прямо сейчас представьте, что это поле из 512 пар <9-битный индекс, прямой адрес>, которое должно быть очень быстрым (только один вызов NULL-проверки и разыменования соответственно).

Как правило, ответ на ваш вопрос также зависит от того, какие другие операции вы хотите выполнить в своей структуре и как часто каждая из них (включая возможность поиска). Если все, что вам нужно, это поиск (9 бит) -> добавить / изменить / прочитать, структура вашего блока будет бесполезной. Вы можете написать их здесь и, возможно, добавить, какой язык вы используете.

Изменить 3: Я только заметил, что вы не можете изменить размер блоков. Но вы ищете только из соображений эффективности, или вам нужно, чтобы элементы списка были уникальными (по этим 9 битам)?

1 голос
/ 01 декабря 2010

Пусть количество элементов в каждом блоке равно m, а общее количество блоков в списке в данный момент равно n.Тогда сложность текущего алгоритма вашего времени O (n log m).

Если вы не можете перемещать элементы после их добавления в блок, то я не думаю, что вы сможете добиться большего успеха в плане сложности времени, чем то, что вы уже делаете.(Вы можете отслеживать максимальный и минимальный элементы в блоке и пропускать блоки, если элемент не лежит в этом диапазоне. Но это не даст вам большого выигрыша. Это также приведет к потере места, отслеживая минимуми максимум для каждого блока)

Если вы можете позволить себе тратить время на вставку элемента и можете перемещать элементы из одного блока в другой, то вот схема, которая имеет временную сложность O (log (mn)).

По сути, вы сохраняете все элементы в отсортированном порядке.Когда новый элемент должен быть вставлен, бинарный поиск через границы блока и вставьте его в правильное место, сдвигая элементы, чтобы создать пространство.Это приведет к времени O (нм) при вставке элементов, но O (log (mn)) при поиске элемента.

...