Описание тега skip-lists
A skip list is a probabilistic data structure for storing and retrieving sorted data.
1
ответ
Метод PHP SkipList put всегда возвращает ноль
Я пытаюсь реализовать список пропуска в PHP с использованием псевдокода из http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html. Мне удалось заставить его работать нормально в Java, но не в PHP. Мой метод put всегда возвр…
26 дек '15 в 03:26
3
ответа
Как называется этот алгоритм поиска?
Недавно я столкнулся с алгоритмом поиска чисел в отсортированном списке, и вот как он работает: Дано: оракул, который сообщает вам, является ли данное число большим или меньшим, чем искомое число. Начните с первого элемента в списке. Пропустите 1 эл…
25 май '13 в 15:15
1
ответ
Сложность ConcurrentSkipListSet для доступа к первым и последним элементам
Из того, что я понимаю, ConcurrentSkipListSet имеет среднюю сложность O(log n) для вставки, поиска и удаления элементов и наихудший вариант O(n). Как насчет доступа к первому и последнему элементу? Это ниже, чем журнал? Я вижу, что он сохраняет указ…
19 фев '15 в 15:10
2
ответа
Почему не существует не одновременной версии SkipList
Я начал исследование ConcurrentSkipListSet. С самого начала я пытался понять, что такое SkipList? Я представляю это так (возможный вариант): У меня есть 2 вопроса: Как SkipList связан с параллелизмом? Почему не существует одновременного варианта это…
27 май '14 в 12:29
3
ответа
Почему списки пропусков не предпочтительнее деревьев B+ для баз данных?
Я читал о списках пропусков и MemSQL, и мне было интересно, почему списки пропусков не так широко используются в базах данных? Существуют ли серьезные недостатки в использовании скиплистов?
17 фев '14 в 12:14
1
ответ
Приложения, использующие коллекции Java
Есть ли способ найти какое-нибудь Java-приложение, которое использует определенную коллекцию. Я реализовал свой собственный список одновременных пропусков и хотел "заменить" его в приложение, где ConcurrentSkipListSet коллекций Java используется, чт…
09 дек '13 в 11:16
3
ответа
Удалить 10000-й узел в связанном списке
У меня есть связанный список из n узлов, я хочу удалить k-й узел и отобразить элемент в нем. Это легко, если значение n относительно мало и сложность проблемы не является проблемой. Проблема в том, что у меня есть n узлов в связанном списке, где n >…
13 окт '16 в 05:29
0
ответов
Как хранить списки пропусков на диске?
Как вы храните список пропусков на диске? Как вы упорядочиваете узлы, чтобы использовать преимущества страниц файловой системы? Используете ли вы файл для каждой страницы, один файл для всего или что-то еще? В связанном вопросе упоминаются указатели…
10 дек '18 в 14:47
1
ответ
Почему моя временная сложность вставки в список пропусков линейна?
Я реализовал список пропуска для целых чисел. При тестировании метода вставки я вставляю натуральные числа от 1 до 1000000 в цикл for со счетчиком j. Я также использую секундомер. Приложение: в реальной программе значения удваиваются, потому что я и…
15 апр '13 в 06:15
0
ответов
Как сделать так, чтобы все узлы графа в графике начинались на одном горизонтальном уровне?
Я пытаюсь отобразить структуру данных skiplist в graphviz. Как сделать так, чтобы все узлы графика начинались с одинаковой горизонтальной высоты вместо случайных положений узлов?
01 сен '15 в 16:47
3
ответа
Ожидаемое потребление места в списках пропусков
Какое ожидаемое пространство используется списком пропуска после вставки n элементов? Я ожидаю, что в худшем случае потребление пространства может возрасти до бесконечности. Википедия говорит "Космос O(n)". Как это может быть доказано так или иначе?
06 май '12 в 15:08
1
ответ
Ошибка сегмента STL, как реализация списка пропусков
Я реализовывал скип-лист в стиле STL. Тип внутреннего узла выглядит так: template <class N> struct __skiplist_node { typedef __skiplist_node<N>* __skiplist_node_pointer; N data; __skiplist_node_pointer prev; std::list<__skiplist_node_…
08 июл '14 в 06:58
2
ответа
Равномерно размещенные указатели Skip
Я читал об указателях пропуска, и кто-то предположил, что лучше всего помещать указатели пропуска с равным интервалом sqrt(len of list). Может кто-нибудь сказать мне, что здесь означает "равномерно распределенный"? Я также хотел бы видеть код, делаю…
22 фев '11 в 13:50
1
ответ
Почему есть ConcurrentSkipListMap, но нет несинхронизированной версии?
Большинство классов в Java Collections Framework по умолчанию не синхронизированы, но могут быть преобразованы во что-то синхронизированное, если вам нужно, чтобы они были поточно-ориентированными. Синхронизация снижает производительность, поэтому, …
13 ноя '14 в 20:00
1
ответ
Мелкозернистая блокировка в Skip List
Я пытаюсь реализовать основанный на блокировке skiplist в c, используя мелкозернистый механизм блокировки. При запуске кода применяемый механизм блокировки выглядит грубым. Я вставил блокировки в предыдущие узлы для вставки, используя переменную бло…
04 дек '14 в 12:10
1
ответ
Лучше, чем ConcurrentSkipListSet, если я не хочу сопоставимый IF
У меня горячая дискуссия с коллегой, потому что он не хочет признать, что лучше использовать существующие классы из пакета Java, чем писать свои собственные. Мы хотим получить доступ к набору потокобезопасным способом, чтобы итераторы также работали…
28 сен '15 в 09:23
1
ответ
Слияние пропущенных списков
Как я могу объединить 2 данных Skip lists (каждый с n клавишами) в один Skip List в O(n) сложность времени (наихудший случай)? Просто ищу алгоритм - никакой конкретной реализации / языка.
08 май '11 в 08:19
0
ответов
Как реализовать алгоритм LRU с помощью Skip List?
В нормальных условиях use Мы используем Link List для реализации LRU, но как реализовать LRU с помощью Skip List?
13 июн '18 в 03:28
1
ответ
Как найти исключение в методе?
Мой класс структур данных работает над реализацией своей собственной структуры данных в форме SkipList. Метод, над которым я работаю, это subList. Я обработал большинство ошибок, но я получаю сообщение о том, что в моем исключении testSubList() мето…
31 окт '17 в 21:25
3
ответа
SkipList<T> против словаря<TKey, TValue>
В последнее время я читаю о Skip Lists. У меня есть веб-приложение, которое выполняет довольно сложные запросы Sql к статическим наборам данных. Я хочу реализовать систему кеширования, в которой я генерирую хэш md5 для запроса sql, а затем возвращаю…
13 сен '10 в 01:34