199 ответов в теме

[Delit]

Но как это отменяет операцию поиска по этому самому индексу ??? Что такое по твоему индекс? Волшебник который по заданному числу мгновенно указывает место положение данных ?

Угу, так и есть, ну почти так

[Lantitudia]

Угу, так и есть, ну почти так

Вот, на пример, отсортированный индекс: 1 30 478 6666 9997 4294967296.
Дано число, которое заведомо в этом индексе есть.
Написать алгоритм возвращающий по этому числу его позицию в индексе.
Требования: производительность алгоритма не выше О(1), т.е. не зависит от N и не производит никакого "поиска" - как предполагал Yaponiz.
Должен работать для любого N. N - это количество элементов в индексе и его размерность 64-ре бита.

[myst]

Требования: сложность алгоритма не выше О(1), т.е. не зависит от N и не производит никакого "поиска".

Не зависит от N -- это одно, не делает никакого поиска -- это другое. См. hash table.

[Lantitudia]

Не зависит от N -- это одно, не делает никакого поиска -- это другое. См. hash table.

Ты бы посмотрел на тип ключей который там приведен - и каков результат хэш-функции.

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

Допустим хэшь функция отразит множество 2^64 равномерно на множество 0 - 2^M . Что бы это 2^M "указателей" можно было бы уместить в оперативе. Это означает что на каждый из 2^M придется 2^64/2^M элементов. А это будет очень много. И по каждому результату хэшь функции - снова поиск.

Конкретный алгоритм хэшь функции плиз. Что такое хешь таблица я знаю. =)

[paagrio]

Сори что вытянул старый пост, но очень хотелось на него ответить.

Мне вот интересно. Выпущеная кораблем ракета и летящая к цели ведь тоже имеет свой ID. Любопытно что делает скрипт с ней.

Да, каждая выпущеная ракета имеет свой ID и мониторится в рпоцесе полета. Собственно поетому девы внесли изменения в файтер-бомберы (ссилко http://www.eveonline...a=blog&bid=809)

Not only are they drones which usually come in packs of 20 per ship but they fire missiles which all have to be tracked in the inventory and physical scene within the game.

To alleviate this, we are switching fighter bombers to use "fake missiles".

В плане скрипта ето означало, AFAIK, что на короткое время(время полета) создавался(а потом удалялся) ID ракеты, а учитывая нехватку ID над каждой ракетой выполнялся данный скрипт. Я не знаю скорострельности Ф-Б но тут просто понять что данная штуковина - корень лагогенерации. Другого пути для столь частогго вызова скрипта я не вижу.

Сообщение отредактировал paagrio: 08 November 2010 - 21:33

[myst]

Конкретный алгоритм хэш-функции плиз. Что такое хеш-таблица я знаю. =)

Ты просил способ поиска по ключу, который не зависит от N. Я тебе его показал.

P.S. Внеклассное чтение.

[Lantitudia]

Ты просил способ поиска по ключу, который не зависит от N. Я тебе его показал.

P.S. Внеклассное чтение.

А ты сам то ссылку читал или тебе объяснить что там написано ?

[Kil]

Всякий, кто считает, что Python приспособлен для написания таких систем... просто наивный человек.

Всякий, кто считает, что Ева написана на чистом Питоне, просто наивный человек.
Гоу учить матчасть и учиться, наконец, понимать разницу между Python и Stackless Python, а потом уже выдавать свои глубокомысленные комментарии.

[Slotos]

Проблема в том, что нода EvE должна представлять собой вычислительную систему реального времени.

Да ну прямо таки система наведения, а не ММО получается. Может ещё аналоговые компьютеры посоветуете использовать?

[Nonones]

Всякий, кто считает, что Python приспособлен для написания таких систем... просто наивный человек.

А ещё они убили Кенни используют MSSQL!!!

Всякий, кто считает, что Ева написана на чистом Питоне, просто наивный человек.

Есть более наивные люди, которые считают что если переписать Еву на ассемблере то лагов не будет

Сообщение отредактировал Nonones: 09 November 2010 - 13:54

[Lantitudia]

Ты просил способ поиска по ключу, который не зависит от N. Я тебе его показал.

P.S. Внеклассное чтение.

Видимо придется ответить.

По ссылке приведены алгоритмы хэш функций, которые действительно позволяют производить поиск не зависящий по времени от количества элементов (N). Собственно, это очевидное применение хэш-таблиц - главное и самое сложное грамотно подобрать хэш-функцию.

Но есть одно но. Авторы прямо и пишут, что для индексирования баз данных с частыми добавлениями и удалениями элементов очень хорошо работают бинарные-деревья (сбалансированные, разумеется). А приведенные хэш-функции авторы рекомендуют для баз данных где множество идов либо статично (неизменно) либо редко меняется - но требуется огромная скорость доступа-поиска:

Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets, such as words in natural languages, reserved words in programming languages or interactive systems, universal resource locations (URLs) in Web search engines, or item sets in data mining techniques. Therefore, there are applications for minimal perfect hash functions in information retrieval systems, database systems, language translation systems, electronic commerce systems, compilers, operating systems, among others.

...

Probably, the most interesting application for minimal perfect hash functions is its use as an indexing structure for databases. The most popular data structure used as an indexing structure in databases is the B+ tree. In fact, the B+ tree is very used for dynamic applications with frequent insertions and deletions of records. However, for applications with sporadic modifications and a huge number of queries the B+ tree is not the best option, because practical deployments of this structure are extremely complex, and perform poorly with very large sets of keys such as those required for the new frontiers database applications.

Очевидно БД Евы требуется очень частая вставка/удаление идов. Поэтому эти хеш-функции не применимы. А удобны бинарные-деревья (как вариант). А время поиска по бинарному дереву завист от N, оно много меньше O(N), но все же зависит.

Да и вообще, применять хэш-таблицы ко множеству int64 (множеству с заранее не известным распределением) - идея просто абсурдная еще по множеству причин. И все они сводятся к невозможности написать эффективную хэш-функцию.

Собственно, господину myst-у я рекомендую почитать книгу по базовым алгоритмам и структурам данных.

[myst]

Написать алгоритм, возвращающий по этому числу его позицию в индексе.

Ты просил пример. Я тебе пример привёл. Что не так?

[Lantitudia]

Ты просил пример. Я тебе пример привёл. Что не так?

Да, пример просил - но пример по теме разговора, а не из совсем другой области применимости.

Разве это не очевидно ?

[myst]

Какой теме? Блог неточно переведён?

[Lantitudia]

Какой теме? Блог неточно переведён?

По теме применимости тех или иных алгоритмов оптимизации поиска в случае БД Евы.

Ты привел алгоритмы оптимизации поиска применимые к БД в которых вставка/удаления достаточно редки. Это явно не случай Евы.

Т.е. ты выразился не по теме.

Ты специально из себя дурачка строишь?

[Nonones]

И это тоже СУБД Oracle не только мощнее и гибче MS SQL, но компания Oracle также предлагает законченную платформу: от железа до ОС и самой СУБД, чего у Microsoft никогда не было, нет и никогда не будет.

Ещё один администратор баз данных по переписке
Ну расскажите чем Оракл лучше MSSQL. Я с удовольствием послушаю.

[Telsa GirlII]

Напиши свою EVE с блэкджеком и шлюхами на C++ и Oracle! Делов-то!