Пропустите Списки — когда-нибудь использовал их?
Исключение нулевого указателя генерируется, когда приложение пытается использовать null в случае, когда требуется объект. К ним относятся:
- Вызов метода экземпляра объекта
null. - Доступ или изменение поля объекта
null. - Принимая длину
null, как если бы это был массив. - Доступ или изменение слотов
null, как если бы это был массив. - Бросок
nullкак будто это было значение Throwable.
Приложения должны бросать экземпляры этого класса, чтобы указать на другие незаконные использования объекта null.
Ссылка: http://docs.oracle.com/javase/8/docs/api/java/lang/NullPointerException.html
5 ответов
Несколько лет назад я реализовал свое собственное для вероятностного класса алгоритмов. Я не знаю ни о каких реализациях библиотеки, но это было долгое время. Довольно просто реализовать. Как я вспоминаю, они имели некоторые действительно хорошие свойства для больших наборов данных и избежали некоторых проблем изменения баланса. Я думаю, что реализация также более проста, чем двоичные попытки в целом. Существует хорошее обсуждение и некоторый демонстрационный код C++ здесь:
http://www.ddj.us/cpp/184403579?pgno=1
существует также апплет с рабочей демонстрацией. Милый блеск Java 90-х здесь:
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
Мое понимание - то, что они не так полезная альтернатива двоичные деревья (например, красно-черные деревья), как они к B-деревья для использования базы данных, так, чтобы можно было подавить # уровней к выполнимому минимуму и иметь дело журналы основы-K w/, а не основывать 2 журнала для рабочих характеристик. В алгоритмах для вероятностных списков пропуска (по моему скромному мнению), легче разобраться, чем соответствующие алгоритмы B-дерева. Плюс существует некоторая литература по свободным от блокировок спискам пропуска. Я посмотрел на использование их несколько месяцев назад, но затем отказался от попытки при обнаружении библиотека HDF5.
литература по предмету:
Статьи Bill Pugh:
- А пропускают поваренную книгу списка
- списки Пропуска: вероятностная альтернатива сбалансированным деревьям
- Параллельное обслуживание Списков Пропуска
неакадемические бумаги/учебные руководства:
- Вечно Confuzzled (имеет некоторое обсуждение нескольких структур данных)
- "Списки Пропуска" Thomas A. Anastasio
На самом деле, для одного из моих проектов, я реализую свой собственный полный STL. И я использовал skiplist для реализации моего std::map. Причина я пошел с ним, состоит в том, что это - простой алгоритм, который является очень близко к производительности сбалансированного дерева, но имеет очень более простые итеративные возможности.
кроме того, Qt4 QMap был skiplist также, который был исходным вдохновением для моего использования его в моем std::map.
Java 1.6 (Java SE 6) представил ConcurrentSkipListSet и ConcurrentSkipListMap к платформе наборов. Так, я размышлял бы, что кто-то там действительно использует их.
Skiplists склонны предлагать намного меньше конкуренции для, привязывает многопоточную ситуацию, и (вероятностно) имейте рабочие характеристики, подобные деревьям.
См. исходная бумага [PDF] William Pugh.
Я реализовал вариант, что я назвал Обратный Список Пропуска для механизма правил несколько лет назад. Почти такой же, но ссылки, выполненные назад от последнего элемента.
Это вызвано тем, что это было быстрее для вставки отсортированных объектов, которые были наиболее вероятными к бэкенду набора.
Это было записано в C# и взяло несколько повторений для получения работы успешно.