Comments 20
задача была решена как мне хотелось : так , как не делают обычно, и как делать не стоит
Вставьте это как дисклеймер к статье:)
Я хз как там в джаве строки хранятся ( UTF-16?), но ASCII и UTF-8 тут явно не к месту
А если "сигнатуры" считать на ГПУ, это не позволит ускорить сортировку относительно классических способов?
Классический способ естественно лучше... Но здесь возможна передача данных сигнатур через сеть, нечто вроде криптографии... Плюс у каждой строки может быть бесконечное количество сигнатур. Т.е. хранимые словари можно менять динамически.... В общем, задача скорее для упражнения ума, чем для практики. Но...... могут быть варианты
Как насчёт сортировки трёх строк: "абв", "а0в", и "а5в" (именно в нижнем регистре)?
Ситуаций когда все строки гарантированно из одного блока Unicode на практике почти не бывает. Разве что если ваша строка из чистого ASCII (0x00020-0x0007E). Даже без цифр в русском тексте неизбежно будут пробелы, точки, запятые, и прочие символы из других блоков, так что отбрасывание старшего байта char приведёт к неверной сортировке. И это ещё без учёта суррогатных пар, нормализации, и прочих прелестей.
Здесь Вы правы. Символы должны быть из одной таблицы. Если символы из одной таблицы, то ничего не мешает отсортировать их.... Класс был сделан для всех символов таблицы.... от 0 до 255 ... Пробелы я конечно не учитывал. Но в принципе ничто не мешает их учесть, так же как их профильтровать знаки препинания и прочее... Да и решал я ее в принципе для слов , а не текста.... Чисто умозрительная задача, которая практического применения вряд ли будет иметь.... ))))
А насколько объем памяти необходимый для хранения сигнатур меньше чем объем памяти необходимый для хранения строк? Есть ли выйгрыш? Если сигнатуры длиннее исходных строк, то в общем случае при сортировке сравнить две сигнатуры будет не дешевле чем две строки.
Мда… А откуда у вас там взялось число 257? Не смущает, что оно очень близко к 256?
Почитайте, что ли про системы счисления. Все вам сразу станет понятно.
Эта ваша сигнатура — это просто интерпретация строки, как числа, записанного в 256-ричной системе счисления. 256, потому что значений у символа может быть столько.
Вот только это все вообще не несет в себе никакого смысла. Потому что biginteger под капотом все-равно будет хранить эти данные в виде строки байт. И мне вообще кажется, что там тоже будет использоватся 256-ричная система счисления, а значит там в памяти будет лежать вот эта же самая строка. И все сравнения будут выполнятся точно также как и со строками. Спрашивается, зачем все это?
256 - размер таблицы ASCII Алгоритм требует этого. Если делать только по буквам и цифрам, то его можно существенно уменьшить. Насчет Бигинтежер Вы правы.... Но здесь возможно кодирование словарей динамически.... А вот насчет зачем все это, то склонен с Вами согласиться..
Вы правы про системы счисления. Про biginteger тоже. От себя могу сказать только то, что для любой строки может быть бесконечное количество отображений в виде числа В зависимости от основы. Я ничего не хотел доказать, просто попробовал. А число 257 меня совершенно не смущает, потому что оно находится рядом с 256. Именно поэтому я его применял. Простите, если был не корректен....
"Эта ваша сигнатура — это просто интерпретация строки, как числа, записанного в 256-ричной системе счисления. 256, потому что значений у символа может быть столько." - Вы здесь очень похоже заметили. Только ввиду своей молодости, подозреваю, просто не увидели, что формирование числа идет не из низших разрядов, как это делается в системах счисления, а из высших. В общем наоборот.... Но все равно я Вам очень благодарен, что Вы хотя бы что то попытались прочитать и понять.... Не спешите, тогда успеете........... Про системы счисления я читал и даже читал лекции лет 30 с хвостиком назад. Очень подозреваю, что Вы тогда еще не родились.... Желаю удачи Вам.
Вот это наезд. Аппеляция к возрасту — такое себе. Особенно на ресурсе про IT. Давайте может чем-то более релевантным похвастаемся? Есть у вас какие-нибудь достижения в спортивном программировании, статьи в международных журналах, работа в ведущей IT фирме, например? Или кроме возраста хвастаться нечем?
От того, что вы с другой стороны будете формировать ваш "хеш", суть не меняется. Но кстати, вы и не заметили, что у вас, таки, первые символы строки войдут с большей степенью 257 в ответ. Так что все как в системах счисления. У вас там, правда, через выворот все сделано и вы вместо домножения на основание берете большое число и делите его на основание системы счисления. Вот и получается, что проходясь по строке в прямом порядке, но считая степени в обратном вы получаете тот же результат, что и система счисления, домноженный на константу.
Здесь Вы правы. Благодарю Вас за внимательность. Спортивное программирование для меня было всегда недоступно. Хотя, в прошлом месяце решил одну задачу из европейской олимпиады по программированию. Это очень интересное занятие. Вообще, в 90 е годы и 2000е мне пришлось заниматься совсем другими делами. Поэтому похвастаться ничем не могу... Работать в 1995 году за 30 долларов в месяц для меня было унизительно, поэтому пришлось делать совсем другое, то , что приносило более высокий доход.... Но Вы были единственный из прочитавших, кто в этом разобрался. Поэтому прошу Вас принять мое уважение.... Всего Вам хорошего.
Нет, не придумал. И , думаю, этого не стоило делать.... Хотя, это позволяет динамически кодировать словари слов в рантайме...... Думаю, что такое никому не надо
Вы это чего, придумали N-значную систему счисления? =) Ну так и берите вес как n^i.
Там есть правило. Вес символа любого должен быть больше сумм всех весов , следующих за ним..... Тогда это работает....
Вычисление сигнатуры строки для её применения в сортировке строк в алфавитном порядке по всем символам