Вам не ясно, или мне? :) Я прочитал, как in работает.
Видимо, мы друг друга не поняли: я говорил о предложенном автором способе организации множества, а Вы — просто об ассоциативных массивах. Для меня как раз очевидно, чем отличается ключ от значения, я много раз использовал эту структуру на разных языках. Я знаю, что данные затираются; знаю, что есть специальная структура multimap (например, в C++), в которой этого не происходит.
Мы создаём объект, который мы будем использовать как хеш-таблицу, в нём — 2 поля. Объект, в контексте статьи, соответствует множеству из 2-х элементов — field1 & field2; проверяем: field1 есть, а, например, field9 — нету. На всякий случай проверяем значения полей: 1 и 2, как ожидалось.
Если, как Вы утверждаете, при совпадении хешей значения затираются, то можно найти бесконечное множество таких строк взамен «field2» и «field9», что второй алерт выведет true, а четвёртый — 2. Но ведь это же глупость, потому что в таком случае нельзя использовать объекты вообще — вдруг хеши имён совпадут, как я указывал.
Кроме того, вот эта страница убеждает меня, что я правильно понял замысел автора и принцип работы in.
Коллизия в данном случае не страшна. Способ хорош по производительности, но немного неочевиден для чтения.
Я, наверное, не так понял: автор предлагает использовать хеш в форме ключ-имя поля, значение-значение поля? Вроде про {} речи не идёт, или in не проверяет то, что у объекта есть такое поле?
Не все рекурсивные алгоритмы можно развернуть в цикл :) (в основном так называемую «хвостовую рекурсию»). Однако, как некоторые здесь замечали, от любой рекурсии можно избавиться, заменив автоматическое использование стека явным (например, самописным на массиве).
Вы думаете, что JavaScript не проверяет строки после поиска в таблице с помощью точного сравнения? Ну тогда просто опасно пользоваться таким языком — можно, ничего не подозревая, обратиться вместо field1 к field2, или вызвать не тот метод, если хеши их названий совпадут… ;)
На самом деле, в таких случаях в ячейке хеш-таблицы находится не один объект (иначе бы объекты с равными хешами затирали бы друг друга уже при добавлении!), а список — и в нём, в очень маленьком списке, ищется объект среди других, с тем же значением хеш-функции.
Ну конечно, у двух предложенных вариантов будет разная скорость — у них просто разная вычислительная сложность.
У поиска подстроки — О(размер склеенной строки + размер искомой строки) для алгоритма КМП.
У обращения к полю (почти наверняка оно реализовано хеш-таблицей) — О(1), т. е. просто-напросто (амортизированное) константное, наименьшее возможное, что достигается бОльшим расходом памяти (размен времени на память). Плюс время вычисления хеша, оно О(длина строки), но вычисляется он очень быстро.
А вот линейный поиск (indexOf), понятно, имеет линейную сложность по поиску, умноженную на сложность сравнения строк (его сложность О(длина искомой подстроки)).
Кроме хеш-таблиц, для хранения множеств (в том числе упорядоченных) также используют сбалансированные деревья (не знаю, есть ли в JavaScript), у них сложность основных операций О(log(число элементов в множестве)), что обычно несколько хуже, чем хеш. Эту сложность так же следует умножить на сложность сравнения строк (оно линейно, О(длины строки)).
Сейчас прочитал, что tar использует внешние программы для упаковки результатов своего труда :). Но, всё же, делает это совершенно прозрачно для пользователя.
Команда tar, кстати, почти такая же старая — изначально она предназначена для работы с бэкапами на магнитных лентах (объединяя множество файлов в один и записывая его), а сейчас используется как самый распространённый архиватор для Unix-систем, поддерживая сжатия gz, bz, и другие возможности.
Обычное дело, часто такое вижу в студенческих прогах: просто механическая запись условия задания в код, когда не выспался да не понимаешь, ещё не то напишешь. А ещё бывают перлы типа
if (l[0]+l[1]+l[2]+l[3]+l[4]=='i'+'n'+'p'+'u'+'t')
вместо strncmp и sizeof вместо strlen :), но это немного из другой оперы…
Никогда не слышал про резонансную частоту воды… И на Википедии написано, что частота излучения микроволновки зафиксирована просто, чтоб не создавать помех, а ВЧ-излучение нагревает любой диэлектрик (даже тарелку, хотя намного хуже жидкости, у которой молекулы подвижнее).
Ну, ведь информация - не вещь, как известно: её можно скопировать, изменить, удалить бесследно (не надо про субатомный магнитный анализ :). Я же говорю, что если блоки сделать по 2 байта (чисто теоретически), то доказать что-то просто невозможно (а блоков таких всего будет 256^2 - экономия диска в обмен на офигенные ссылки :) - ну кто отличит вот эти "АБ" из образа диска MSOffice от тех "АБ" из Шекспировской трагедии?
Я считаю, идея очень хороша: действительно, кто докажет, что конкретные 128 килобайт из конкретной МП3-шки, а не от зашифрованного диска? Чем меньше куски, тем меньше вероятность (в пределе несколько байт - для бинарников там будут попадаться даже куски осмысленного текста). Хотя, в суде всё будет зависеть от позиции судей и адвокатов: смогут ли они доказать, что набор бессмысленных файлов на винте - контрафактный продукт? Думаю, в большинстве случаев такой набор будет трактоваться против обвиняемого (логика: если скрывает, значит, что-то нечисто).
Видимо, мы друг друга не поняли: я говорил о предложенном автором способе организации множества, а Вы — просто об ассоциативных массивах. Для меня как раз очевидно, чем отличается ключ от значения, я много раз использовал эту структуру на разных языках. Я знаю, что данные затираются; знаю, что есть специальная структура multimap (например, в C++), в которой этого не происходит.
Вопрос, по-видимому, исчерпан?
var obj = new Object();
obj.field1 = "1";
obj.field2 = "2";
window.alert("field1" in obj);
window.alert("field9" in obj);
window.alert(obj.field1);
window.alert(obj.field2);
Мы создаём объект, который мы будем использовать как хеш-таблицу, в нём — 2 поля. Объект, в контексте статьи, соответствует множеству из 2-х элементов — field1 & field2; проверяем: field1 есть, а, например, field9 — нету. На всякий случай проверяем значения полей: 1 и 2, как ожидалось.
Если, как Вы утверждаете, при совпадении хешей значения затираются, то можно найти бесконечное множество таких строк взамен «field2» и «field9», что второй алерт выведет true, а четвёртый — 2. Но ведь это же глупость, потому что в таком случае нельзя использовать объекты вообще — вдруг хеши имён совпадут, как я указывал.
Кроме того, вот эта страница убеждает меня, что я правильно понял замысел автора и принцип работы in.
Коллизия в данном случае не страшна. Способ хорош по производительности, но немного неочевиден для чтения.
На самом деле, в таких случаях в ячейке хеш-таблицы находится не один объект (иначе бы объекты с равными хешами затирали бы друг друга уже при добавлении!), а список — и в нём, в очень маленьком списке, ищется объект среди других, с тем же значением хеш-функции.
У поиска подстроки — О(размер склеенной строки + размер искомой строки) для алгоритма КМП.
У обращения к полю (почти наверняка оно реализовано хеш-таблицей) — О(1), т. е. просто-напросто (амортизированное) константное, наименьшее возможное, что достигается бОльшим расходом памяти (размен времени на память). Плюс время вычисления хеша, оно О(длина строки), но вычисляется он очень быстро.
А вот линейный поиск (indexOf), понятно, имеет линейную сложность по поиску, умноженную на сложность сравнения строк (его сложность О(длина искомой подстроки)).
Кроме хеш-таблиц, для хранения множеств (в том числе упорядоченных) также используют сбалансированные деревья (не знаю, есть ли в JavaScript), у них сложность основных операций О(log(число элементов в множестве)), что обычно несколько хуже, чем хеш. Эту сложность так же следует умножить на сложность сравнения строк (оно линейно, О(длины строки)).
А если серьёзно, то странно, что это слово попало в события, тем более что вся первая страница посвящена группе, а не празднику…
«The name „Tar“ comes from this use; it stands for tape archiver.» — www.gnu.org/software/tar/