|
1182 / 624 / 160
Регистрация: 19.04.2018
Сообщений: 2,923
|
|
Найти самую повторяющуюся букву в фразе31.07.2021, 16:31. Показов 9785. Ответов 54
Метки нет (Все метки)
Здравствуйте. Недавно писал решение задачи с поиском повторяющейся буквы(и сколько раз). Для этого мне пришлось сделать 2 итерации
- Как можно ускорить алгоритм? - Можно ли сделать всё в одну строку(например через Linq)? Добавлено через 55 секунд Например решением для фразы "Hello world!" ответом будет "l" — 3 раза.
0
|
|
| 31.07.2021, 16:31 | |
|
Ответы с готовыми решениями:
54
Найти самую повторяющуюся цифру в массиве цифр |
|
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
|
||
| 05.08.2021, 20:06 | ||
|
Kazbek17, сортировку забыли.
Добавлено через 1 минуту
0
|
||
|
3566 / 2507 / 1174
Регистрация: 14.08.2016
Сообщений: 8,219
|
||||||
| 06.08.2021, 21:14 | ||||||
0
|
||||||
|
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
|
|
| 07.08.2021, 09:01 | |
|
Ну если уж заморочиться скоростью в самых минимальных единицах, то и не словарь, и не Linq. Самый обычный массив. В большинстве случаев в производительности у всех выиграет короткий массив.
В словаре - каждый раз придется проверить, существует ли ключ. Эта проверка делается быстро, но она выполняется на каждой итерации. Можно и не вызывать метод ContainsKey, но словарь все равно будет проверять ключ на null, вызывать Comparer и так далее. Все это дополнительные операции. В массиве ничего проверять не нужно, сразу увеличиваем значение под нужным индексом. Массив здесь будет явно быстрее, хотя дальнейшие операции иногда могут свести это преимущество на нет. Дальнейшие операции - пробежаться по массиву/словарю одним проходом, чтобы найти максимальное значение. И здесь, словарь может оказаться короче массива, а может оказаться значительно короче. Это зависит от длины исходной строки и от набора символов, которые в нее входят. Если различающихся символов в строке мало и строка короткая, то в словаре будет мало значений, их можно быстро перебрать. Массив же будет длиной минимум 128. Если строка короткая, но содержит весь набор символов, то массив выиграет. Если строка длинная, то словарь проигрывает за счет количества операций на каждый символ. И чем длиннее строка, тем более заметна будет разница. На длине в сотни тысяч символов будет на порядок. Один момент, который нужно учесть - в строке символы могут быть разные (из разных языков), и придется использовать массив значительно длиннее 128. В этом случае, если строка короткая - метод со словарем будет работать быстрее. Но если длинная или очень длинная, то на большом количестве операций словарь однозначно проиграет. Linq будет еще медленнее словаря. В словарь символы добавляются за один проход. Идем по строке, проверяем, добавляем или увеличиваем значение. GroupBy подсчета не выполняет, нужен еще один метод - Count. Значит для каждой группы символов еще один проход по группе. Сортировку можно не учитывать, так как ее можно избежать, так же как в случае со словарем и массивом. Вопрос, насколько чувствительно это будет, скажем чтобы не приходилось использовать измерительные средства, чтобы заметить разницу. На длинах примерно до 100 тыс. символов, это порядки тиков. Можно спокойно использовать любой способ, который удобнее, короче, больше нравится, более понятный и так далее. На очень больших длинах (миллионы символов) или очень большом количестве обрабатываемых строк, естественно разница очень даже будет. Но вопрос темы думаю, не о таком случае.
2
|
|
|
Модератор
|
||||||||||
| 08.08.2021, 15:09 | ||||||||||
|
Не по теме:
Аббревиатура из английских символов - сокращение от "Topic Caster". Дословно можно перевести "Тот кто бросил тему (на обсуждение)". По смыслу, конечно, просто "Автор темы". ![]() Добавлено через 15 минут Поскольку на первой итерации (первым циклом) необходимо подсчитать количество вхождения КАЖДОГО символа из последовательности. То есть обязательно возникает пара (символ, количество). Словарь предлагает самый быстрый способ доступа к элементу по индексу отличному от целого числа. На второй итерации (вторым циклом) необходимо выбрать пару с наибольшим значением количества. Здесь так же ничего быстрее линейного перебора не придумаешь. Массив, безусловно, будет быстрее словаря при доступе к единичному элементу. Но для данной задачи придётся для индексов использовать код символа и размер массива (чтобы вошли все коды) должен быть ushort.MaxValue+1 = 216.С таким массивом можно будет ускорить подсчёт количества. Но для выбора максимального значения, придётся перебрать все 216 элементов. А в словаре будут только символы имеющиеся в тексте и он, чаще всего, будет в сотни раз короче массива. Поэтому массив может дать преимущество только если нужна обработка ОЧЕНЬ больших текстов и в этом тексте присутствуют очень много разных символ (количество сопоставимое с 216). Добавлено через 2 минуты Вы и сами сделали подобный вывод. ![]() Добавлено через 8 минут Верное решение увидел только у Diamante (пост #43). Чуть только можно изменить - для вывода не только символа, то и его количества.
1
|
||||||||||
|
|
|||||||
| 08.08.2021, 16:08 | |||||||
1
|
|||||||
|
Модератор
|
||
| 08.08.2021, 16:44 | ||
|
Надо увеличить размер: var arr = new int[ushort.MaxValue + 1];.Но вот сколько займёт в нём поиск максимального? Оправдается ли? Добавлено через 59 секунд И char к int явно, по-моему, не нужно приводить.
0
|
||
|
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
|
||||
| 08.08.2021, 20:24 | ||||
|
По условию задачи, строка вообще - английский текст. Ищем букву. Там хватит массива 128. Понятно, что текст может быть разный, и языки разные, но вряд ли среди них будет Глаголица или Руны . Можно преспокойно ограничиться массивом 0x04FF. чтобы покрыть большинство распространенных алфавитов. А при такой длине массива - у словаря вообще нет шансов ни на каких длинах, даже в 10 символов.
1
|
||||
|
1534 / 541 / 127
Регистрация: 09.01.2018
Сообщений: 1,758
|
|||||||||||
| 09.08.2021, 03:49 | |||||||||||
|
Да и вообще эту проблему можно обойти, сделав все одним проходом.
Вот тест на малых длинах, с максимальной длиной массива и набором из разных блоков BMP:
При увеличении длины сохраняется примерно такое же 4-х кратное превосходство массива.
4
|
|||||||||||
|
1152 / 860 / 263
Регистрация: 30.04.2009
Сообщений: 3,603
|
|
| 09.08.2021, 09:30 | |
|
escoult, автор поста вроде ничего не говорил о возможности исключить арабские буквы, а они в конце таблицы.
0
|
|
|
Модератор
|
||||||||||||
| 09.08.2021, 09:59 | ||||||||||||
|
Мне что-то это не пришло в голову. Нужна же только максимальная комбинация, поэтому нет необходимости в сортировке ПОСЛЕ группировки. Можно делать это сразу при подсчёте элементов. На основе кода от Wolfdp:
2
|
||||||||||||
|
|
|||
| 23.08.2021, 18:59 | |||
0
|
|||
|
Модератор
|
||
| 23.08.2021, 19:56 | ||
|
Спорить не буду - не вижу смысла. Так как в любом случае это означает по смыслу одно и тоже. Наверное имеет значение TC - написано латиницей (то есть ти-си) или кириллицей (то есть тэ-эс).
1
|
||
|
|
||
| 23.08.2021, 20:12 | ||
|
1
|
||
| 23.08.2021, 20:12 | |
|
Найти самую длинную подстроку повторяющуюся в тексте и подсчитать количество символов подстроки
Найти слово в фразе из 3 слов, которое начинаеться на букву "M" найти в тексте самую встречаемую букву Найти в тексте слова, содержащие самую распространенную букву текста Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала.
Ниже прикреплён. . .
|
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F
Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU.
Опрашиваются регистры. . .
|
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка:
Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
|
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо
Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
|
|
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман.
Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
|
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
|
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
|
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ
Основная суть и тезисы по измерениям:
0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема.
Объект не может перемещаться в 0D.
1D (Первое измерение):. . .
|