кусок задачки

[juan_gandhi]

Вот вы, скажем, имплементируете фесбук месенджер. Как вы ключ зададите для чатов? Я предложил (на интервью было) просто пару ключей юзеров. Ну там штука, что симметрично ж должно быть. Интервьюер сказал, что правильно будет брать hash(Set(userid1, userid2)). Меня это как-то удивило; смысл-то понятен, но глупость же.

На самом деле, для симметрии надо просто брать пару ключей да сортировать, например. List(userid1,useri2).sort. И вообще этого мало, нужно еще хранить priority queue из собеседников.

Впрочем, фигня. Обидно другое - это за неделю уже второй облом в смысле контактов. Я, как иной mentally challenged, чуть не каждого первого попавшегося считаю за доброжелательного приятеля - а блин, присмотришься - он тебя ненавидит за каким-то хреном. Как они между собой-то вообще? Не понимаю.

Comments

[snowps.livejournal.com]

Зачем юзерам какие-то отдельные численные идентификаторы, когда любой мессенджер на этапе аутентификации клиента даёт первичный ключ для доступа к ID юзера и все чаты ищутся не по юзерам и их мессаджам, а по простому ID сессии в БД частов (привязанных ко времени, сессии и списку юзеров) конкретного user ID? Сессий намного меньше, чем сообщений, зачем делать индексы для большой таблицы, когда можно обойтись первоначальным фильтрующим обращением к малой? И это ещё без учёта многосессионности, где фильтрация по юзерам вообще работать не будет.

[juan-gandhi.livejournal.com]

Согласен, так гораздо больше смысла.

[slonopotamus.livejournal.com]

Слава ЛММ, еще есть здравый смысл в мире. Читаю соседние ветки комментариев и охреневаю.

[snowps.livejournal.com]

Сформировавшаяся любовь работать со всеми данными исключительно в БД обычно создаёт букет клише, которые приводят к регулярному выбору шаблонных неэффективных database based решений без учёта специфики решаемой задачи. :)

[juan-gandhi.livejournal.com]

Что вы скажете про HTM?

[snowps.livejournal.com]

Что именно имеется в виду - transactional memory или что-то другое?

[juan-gandhi.livejournal.com]

Hierarchical Temporal Memory.

[snowps.livejournal.com]

Раньше термин не попадался, посмотрел - выглядит местами похоже по концепции на алгоритм поиска подстроки, с которым я экспериментировал 15 лет назад. :) Там нужно было быстро определять вхождение повреждённого серийного номера (оторвано начало, конец или доступна толька часть из середины) в гарантийную базу. Поиск в Оракле по %...% был очень долгим, я предложил экспортировать все имеющиеся серийники в несколько файлов, потом грузить их в комп с большим количеством памяти в сплошной массив, состоящий из суммы строк с терминальными символами и делать в нём поиск по четырём байтам ASCII с инкрементом в один байт ассемблерной подпрограммой, в результате чего на выходе в первый заход ставился флаг хотя бы одного вхождения подстроки в отдельных блок данных и далее делалось вычисление индекса искомой записи в файле и только тогда дёргалась БД на предмет подробной информации. Сто тысяч серийников на PIII просматривались за десятки миллисекунд, это было на несколько порядков бысрее работы БД, но так же, как и во многих других случаях, нестандартное решение испугало и народ продолжил мучиться с фуллсканом. :)

[juan-gandhi.livejournal.com]

Да, вот хороший пример.

[slonopotamus.livejournal.com]

Эффективности хотите вы?

int64 userid1, userid2 = ...;
List<int64> ids = [userid1, userid2];
ids.sort();
int128 chatId = (ids[0] << 64) | ids[1];

[juan-gandhi.livejournal.com]

math.max(id1,ud2) << 64 | math.min(id1,id2)

[slonopotamus.livejournal.com]

Ага. И не надо никаких 512-битных хешей.

[juan-gandhi.livejournal.com]

Иному представителю это все не впаришь совершенно. Они ж лучше знают.

[snowps.livejournal.com]

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

[juan-gandhi.livejournal.com]

Да; идея держать пару айди в качестве ключа была ошибкой. Потому хотя бы, что для поиска нужно знать обоих участников. Лучше все эти пойнтеры на чат хранить прямо у участника.