Подходящая структура данных для хранения и расчета элементов с наивысшей оценкой K

Question

Мне нужно хранить W предметов.Каждый элемент имеет атрибут 'string' и атрибут 'double' (оценка элемента), связанный с ним.На каждой итерации дополнительные элементы C добавляются в набор.После завершения итерации, оценка некоторых предметов обновляется на небольшое количество.Теперь из W + C элементов только W должны быть перенесены на следующую итерацию.Будут выбраны предметы с наибольшим количеством очков «W», которые перейдут к следующему поколению.На каждой итерации добавляется различный набор элементов «C».

W имеет порядок 10000.С имеет порядок 600.

Какова лучшая структура данных, чтобы использовать это с точки зрения сложности времени.Хэш-таблица, куча, дерево двоичного поискаЯ использую C ++.Будут оценены некоторые ссылки для повышения

Answer 1

Ну, я думаю, у вас все будет хорошо, если вы просто используете std::vector<Item> и делаете std::nth_element (на счет) один раз в конце итерации. Например. если вы хотите сохранить 10000 предметов, сделайте так:

struct Item {
    double score;
    std::string name;
};

bool comparator(const Item& a, const Item& b) {
    return a.score > b.score;
};

if (items.size() > 10000) {
   // Make sure the 10,000 first elements contain the highest scores.
   items.nth_element(item.begin(), item.begin() + 10000, item.end(),
       comparator);
   // Only keep the first 10,000 elements.
   items.resize(10000);
}

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

Если вы хотите еще более быстрое обновление: перед обновлением отсортируйте элементы по строковому хешу. Затем вы можете выполнить бинарный поиск вместо линейного поиска, чтобы найти элемент, который хотите обновить.

Answer 2

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

Чтобы вставить пару строка / двойка в эту структуру, вы добавляете строку в хеш-таблицу, добавляете двойную к массиву, затем сохраняете указатель на новую строку в массиве и индекс двойного в хеш-таблице.Это имеет сложность O (k), где k - длина строки.

Чтобы изменить приоритет, найдите строку в хеш-таблице, а затем получите индекс типа double в массиве.Затем вы можете изменить этот элемент, чтобы изменить связанный с ним приоритет.Это также имеет сложность O (k).

Чтобы отбросить все, кроме верхних пар ключ / значение B, запустите алгоритм выбора в массиве, чтобы поместить верхние элементы B в одну часть массива и оставшиеся Cэлементы в другом.Всякий раз, когда вы выполняете обмен, следуйте указателям из массива в хеш-таблицу и обновляйте индексы элементов, которые вы только что обменяли.Наконец, выполните итерацию по последним элементам C массива, следуйте их указателям обратно в хеш-таблицу и удалите элементы, на которые они указывают, из таблицы.Это занимает ожидаемое время O (n) для выполнения шага выбора или время O (n) в худшем случае с использованием алгоритма медианы медиан, а затем время O (n) для удаления элементов из хеш-таблицы дляожидаемое время выполнения O (n), где n - количество элементов в структуре.

Подводя итог, можно получить O (k) вставку и поиск любой строки, где k - длина строки, иO (n) сохранение лучших элементов, где n - общее количество элементов.