Вести счетчик вызовов clearAll. По put рядом со значением положить текущее значение счетчика. По get сравнить сохраненное значение с текущим значеним счетчика, вернуть null, если меньше. Простовато для собеседования то.
Также добавлю, что из-за подобного непонимания принципов работы хеш-таблиц (или отсутствия должного внимания к ним) вообще становятся возможными такие вещи как hash collision DoS в каждом втором веб-сервисе. Например, статья на хабре, и более подробная статья.
А вообще, вопросы в статье — чисто джуниорские, для ответа на которые человеку достаточно один раз взять в руки книгу, или, хотя бы, прочитать документацию на Java.
Есть такой плагин интересный для Eclipse — lambda4jdt, который позволяет в IDE визуально сворачивать любой анонимный класс с один методом в лямбда-выражение.
А что, если в один и тот же момент к сервису обратятся сразу два клиента?
Первый — тот, кто собирается на основе данных сервиса хочет сгенерировать ключевую пару, а второй, естественно, злоумышленник.
В таком случае второй сможет неким образом вычислить значение (с учетом завязки сервиса на IP, например), отданное первому клиенту, и успешно сгенерировать у себя такие же ключи.
Логично, что для избежания этого нужно в конкретный момент времени выдавать значение ГСЧ только одному клиенту, но это моментально снижает производительность сервиса.
Время считает, но при нажатии на значок отображается пустое окошко, если мышкой поводить по нему, то некоторые элементы (кнопки) прорисовываются. А ведь так хочется посмотреть, что же там, так хочется, сил нет!
Ubuntu 11.10, Opera 11.52
Кстати, сие решение самое очевидное (сам на красно-черном сделал, но и о списках с пропусками подумал), однако памяти жрет (по сравнению самым простым сортированным массивом) мама не горюй.
Для меня это очевидно из самого определения Trie-метода. Я буду приятно удивлен, если это не так, и, может быть, наконец, увижу хоть какие-нибудь результаты его сравнительного тестирования.
Если не говорить о том, что то, что вы описываете — полный абсурд, то я всего лишь хотел понять смысл всего происходящего, и так как я не могу получить нормального описания алгоритма, то мне нужен код.
И да — метод n-грамм не является методом сравнения слова.
Это всё какие-то абсолютно бессмысленные процедуры. Я всё же хочу ознакомится с каким-нибудь подобием кода или чего-нибудь такого, чтобы начать наконец понимать идею.
1. Что такое норма и как я могу её посчитать от одного слова?
2. Даже если я для слов разной длины раздельно проиндексирую методом хеширования по сигнатуре, то как я во время поиска к результирующему множеству (которое будет состоять из слов длины +-k с хешами, отличными не более чем на k от хеша запроса) применю метод n-грамм?
Я абсолютно ничего не понял. Ведь для того, чтобы использовать какой-то метод в процессе самого поиска, надо предварительно соответствующим этому методу образом подготовить индекс.
Хочу увидеть рабочее решение (или хотя бы внятный алгоритм).
Хотелось бы конечно получить более детальное описание этого алгоритма, чтобы было понятно, к чему такие сложности.
Кроме того, как можно видеть из тестирования, метод N-грамм позволяет на словаре из 3200000 слов (что в 16 раз больше, чем приведенный вами пример) проводить поиск за 1 / 20 секунды. Очевидно, что на 200К слов время работы будет соизмеримо меньше (учитывая свойства этого метода).
Вы в раздел тестирования заглядывали? Конечно, скорость работы по сравнению с точным поиском может отличаться на порядок. Но, опять же, и размер индекса, и время собственно поиска остаются в разумных пределах даже для больших словарей.
Рискну предположить, что по ссылке — ни что иное, как метод Расширения выборки (с ранжированием по частоте), который как раз наиболее часто и используется в spell-checker'ах, и обзор которого так же присутствует в статье.
Алгоритмы нечёткого поиска, а не сравнения. Метрики Левенштейна и Дамерау-Левенштейна приведены для того, чтобы показать суть нечёткого сопоставления и разъяснить, как же оно там внутри всё сравнивает. Сами алгоритмы поиска лишь использует эти метрики для своей работы.
Статья же вовсе не о метриках, да и расстояние Джаро-Винклера не является метрикой с математической точки зрения, потому оно затрудняет или делает невозможной реализацию некоторых алгоритмов. Собственно, и используется то оно не часто.
Чего не хватает в java.util.concurrent, дак это класса ConcurrentLinkedHashMap (хотя есть сторонние реализации), который бы позволил эффективно и просто реализовывать кэш со стратегиями типа LRU и прочими.
А вообще, вопросы в статье — чисто джуниорские, для ответа на которые человеку достаточно один раз взять в руки книгу, или, хотя бы, прочитать документацию на Java.
Первый — тот, кто собирается на основе данных сервиса хочет сгенерировать ключевую пару, а второй, естественно, злоумышленник.
В таком случае второй сможет неким образом вычислить значение (с учетом завязки сервиса на IP, например), отданное первому клиенту, и успешно сгенерировать у себя такие же ключи.
Логично, что для избежания этого нужно в конкретный момент времени выдавать значение ГСЧ только одному клиенту, но это моментально снижает производительность сервиса.
Ubuntu 11.10, Opera 11.52
А почему блог не СКБ Контур?Кстати, сие решение самое очевидное (сам на красно-черном сделал, но и о списках с пропусками подумал), однако памяти жрет (по сравнению самым простым сортированным массивом) мама не горюй.
И вообще, вот же оно intern_develop_solutions.pdf
PS: делал ради интереса, заявок никуда не подавал, в порочащих связях замечен не был.
И да — метод n-грамм не является методом сравнения слова.
2. Даже если я для слов разной длины раздельно проиндексирую методом хеширования по сигнатуре, то как я во время поиска к результирующему множеству (которое будет состоять из слов длины +-k с хешами, отличными не более чем на k от хеша запроса) применю метод n-грамм?
Хочу увидеть рабочее решение (или хотя бы внятный алгоритм).
В итоге, в пул попадало каждое Размер словаря / Объем пула слово не короче 3 символов из отсортированного словаря.
Кроме того, как можно видеть из тестирования, метод N-грамм позволяет на словаре из 3200000 слов (что в 16 раз больше, чем приведенный вами пример) проводить поиск за 1 / 20 секунды. Очевидно, что на 200К слов время работы будет соизмеримо меньше (учитывая свойства этого метода).