tag:blogger.com,1999:blog-410416665291724878.post5089829437803215187..comments2022-12-19T13:52:22.907+04:00Comments on >рабочие заметки: Скаляризация Map.get(new CompositeKey(key1, key2, ...))Ruslan Chereminhttp://www.blogger.com/profile/01023948540752159657noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-410416665291724878.post-39184948284658536492016-10-10T10:23:02.826+04:002016-10-10T10:23:02.826+04:00В фейсбуке как-то один из моих друзей написал &quo...В фейсбуке как-то один из моих друзей написал "все-таки после тренажерного зала поднимается тестостерон". Я поинтересовался деталями уровня тестостерона, и выяснилось, что анализ крови-то он, собственно, не проводил, а просто хотел сказать, что после штанги ощутил в себе больше мужского начала :)<br /><br />Когда ты мне рассуждения про энтропию приводишь -- у меня вот такое же ощущение,Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-27410730031439051582016-10-10T02:45:07.252+04:002016-10-10T02:45:07.252+04:00Я имел ввиду число как поток битов. Только в таком...Я имел ввиду число как поток битов. Только в таком ключе оно нас интересует. В -1640531527 соотношение нулей и единиц ближе к 1-1, чем в 37, что дает больше энтропии по формуле. Даже без учета того, что в 37 немногие единицы еще и скучкованы в одном месте.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-35742616319218857912016-10-10T00:08:06.475+04:002016-10-10T00:08:06.475+04:00Кмк, энтропия здесь вообще ни при чем. В том смысл...Кмк, энтропия здесь вообще ни при чем. В том смысле, что с теоретико-информационной точки зрения я здесь не вижу способа отличить 37 от -1640531527. Вот (эмпирическое) рассуждение про преимущественно короткие хэш-коды -- оно меня больше убеждает. <br /><br />С этим интересно, наверное, plumbr-у поработать -- у них же есть хип-дампы многих реальных приложений, как я понимаю. На такой выборке Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-31797107698057330082016-10-09T23:44:10.599+04:002016-10-09T23:44:10.599+04:00Ну скажем https://ru.wikipedia.org/wiki/%D0%98%D0%...Ну скажем https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%8D%D0%BD%D1%82%D1%80%D0%BE%D0%BF%D0%B8%D1%8F<br /><br />Ну энтропию я даже зря приплел. Просто на практике "составляющие" во всяких кортежах и POJO часто маленькие: хеш-коды коротких строк и числа. И если этих составляющих всего 2-3, маленькое * 37 + маленькоеRoman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-28038226255395534602016-10-09T23:29:03.505+04:002016-10-09T23:29:03.505+04:00Я все пытаюсь понять, на каком уровне математическ...Я все пытаюсь понять, на каком уровне математической строгости ты говоришь. Что такое "энтропия числа" например?Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-38455764246871514872016-10-09T23:24:41.323+04:002016-10-09T23:24:41.323+04:00(h = key.hashCode()) ^ (h >>> 16) не стра...(h = key.hashCode()) ^ (h >>> 16) не страшен абсолютно, естественно он обнуляется в каких-то точках, но так любой хеш-код обнуляется в каких-то точках. У 32-битного числа 37 плохая энтропия. Число типа -1640531527 "универсально хреновое", но у него хорошая энтропия, оно лучше 37.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-8036273676896755152016-10-09T22:59:08.867+04:002016-10-09T22:59:08.867+04:00>Таким образом лучше выбирать простой множитель...>Таким образом лучше выбирать простой множитель х такой, что х+1 содержит 2 в наименьшей степени<br /><br />Это интересный поинт, спасибо.Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-81456130594277971752016-10-09T22:51:21.344+04:002016-10-09T22:51:21.344+04:00Слушай, ну это звучит как шаманское заклинание, не...Слушай, ну это звучит как шаманское заклинание, не находишь? Сначала мы подбираем числа с большим кол-вом битов "везде", а потом (h = key.hashCode()) ^ (h >>> 16), и хер его знает, где в итоге окажутся наши биты. <br /><br />Я, еще раз повторюсь, не специалист в этом вопросе. Но у меня пока такое (узко-эмпирическое) мнение, что я либо использую "универсально-хреновую"Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-32151928941965922342016-10-09T22:45:05.167+04:002016-10-09T22:45:05.167+04:00Плохо, когда во множителе много нулевых битов с од...Плохо, когда во множителе много нулевых битов с одной из сторон. У маленького множителя много нулей наверху. У большого простого числа биты везде, это хорошо, никаких минусов.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-75293982584708710422016-10-09T21:58:35.138+04:002016-10-09T21:58:35.138+04:00Про выбор хэш-кода, это отдельная ветка рассуждени...Про выбор хэш-кода, это отдельная ветка рассуждений. Мне кажется, что логика "недостаточно сдвигает в старшие биты" -- она подхачивает текущую реализацию, а не универсально лучше. Потому что "сдвигать в старшие биты" имеет смысл только если у тебя исходные хэшкоды -- в младших битах. А это априори никак не очевидно: у меня так и получилось, да, но это случайность. Если же у Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-86863386415686386282016-10-09T21:48:30.522+04:002016-10-09T21:48:30.522+04:0037 хорошо, но очень мало. Недостаточно сдвигает да...37 хорошо, но очень мало. Недостаточно сдвигает данные в старшие биты. Нужно большое число.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-90207125044724763572016-10-09T21:46:28.985+04:002016-10-09T21:46:28.985+04:00Там не приведен код hashCode(), только equals().
...Там не приведен код hashCode(), только equals().<br /><br />Лучше тем, что хеш коды будут попадать не на кратные 32, а 1000004, что будет давать гораздо меньше коллизий.. кстати это крайне интересный момент, надо раскачать. 31 как раз выбирались 20 лет назад не просто так, а из за близости к степени двойке, что давало оптимизацию умножения. Сейчас положительный эффект исчез, если когда то и был, Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-78608012892364118652016-10-09T15:48:50.210+04:002016-10-09T15:48:50.210+04:00Ищи по ключевым словам "тогда код .equals() д...Ищи по ключевым словам "тогда код .equals() должен быть ну очень коротким, чтобы пролезть под порогом инлайнинга для не горячих методов" :)<br /><br />>Лучше умножай на 1000003, как AutoValue<br /><br />А почему это лучше? В смысле -- я слышал, что 31/37/17 не самые лучшие варианты, но чем 1000003 лучше?<br /><br />Ну и, потом, 1000003 еще знать надо. А IDEA по-умолчанию использует Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-3871479468511207702016-10-09T14:31:12.893+04:002016-10-09T14:31:12.893+04:00Я в упор не вижу, где это приведено в статье?
Луч...Я в упор не вижу, где это приведено в статье?<br /><br />Лучше умножай на 1000003, как AutoValue.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-26348922726071142832016-10-09T14:28:18.710+04:002016-10-09T14:28:18.710+04:00Этот комментарий был удален автором.Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-31904495055769470112016-10-09T12:19:58.815+04:002016-10-09T12:19:58.815+04:00>Я уже наверное спрашивал, почему ты не пишешь ...>Я уже наверное спрашивал, почему ты не пишешь на английском?<br /><br />Стесняюсь мурманского акцента :)Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-81379580738567800872016-10-09T12:18:42.770+04:002016-10-09T12:18:42.770+04:00>Неужели ни одна из пяти реализаций не копипаст...>Неужели ни одна из пяти реализаций не копипастила HashMap с вшиванием key1, key2 в поля Entry и не обновляла сигнатуры по типу get(key1, key2)? Звучит как работа на один день.<br /><br />(Я предпочитаю копипастить trove THashMap, если уж). Но на самом деле не так важно, как именно реализован этот TwoKeyMap -- да, перформанс будет получше, но претензия к неуниверсальности, нерасширямости -- Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-43695707421706894312016-10-09T12:14:42.181+04:002016-10-09T12:14:42.181+04:00Ну, примерно так. Я думаю написать отдельный пост,...Ну, примерно так. Я думаю написать отдельный пост, покороче, про то, что можно с этим поделать -- а то этот и так большой вышел.<br /><br />В целом, на все всегда воля всевышнего -- это же стохастическийдинамический рантаймRuslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-48029234418964109712016-10-09T01:49:41.498+04:002016-10-09T01:49:41.498+04:00Руслан, спасибо за пост. Я уже наверное спрашивал,...Руслан, спасибо за пост. Я уже наверное спрашивал, почему ты не пишешь на английском?<br /><br />> Иногда хочется этого избежать. Тогда приходится организовывать иерархические словари-словарей-словарей... — я видел много таких примеров (поиск по текущему проекту находит аж 5 различных реализаций чего-то вроде TwoKeyMap/ThreeKeyMap). Это решение мне самому не нравится (хотя 2 из 5 упомянутых Roman Leventovhttps://www.blogger.com/profile/18179832405016161004noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-64214050324093204742016-10-09T01:46:01.832+04:002016-10-09T01:46:01.832+04:00Если подытожить - халявы не будет, на всё воля все...Если подытожить - халявы не будет, на всё воля всевышнего (в раскладке ключей)Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.com