Обращение через индекс Dictionary или IndexOf, что быстрее / производительнее?

@VLK · Регистрация: 05.05.2013

Студворк — интернет-сервис помощи студентам

Смотрите есть строка:

C#
1
string dic = "abcdefghijklmnopqrstuvwxyz";

мне приходит символ (char) и мне надо выяснить положение этого символа в строке, у меня есть 2 варианта, первое искать при помощи IndexOf:

C#
1
int pos = dic.IndexOf(MyChar);

или есть второй вариант, изначально dic разбить на список Dictionary<char, int>, короче так:

C#
1
2
Dictionary<char, int> collection = new Dictionary<char, int>();
for (int i = 0; i < dic.Length; i++) collection.Add(dic[i], i);

этот collection будет сохранен как свойство, т.е. на надо будет каждый раз повторять эту "конвертацию".

а потом просто:

C#
1
int pos = collection[MyChar];

как будет быстрее и производительнее?
Работы будет много, по этому это важно.

PS я может туплю, просто в последнее время занимался РНР, а там есть способ так обращаться и оно работает быстрее чем поиск по массиву, вот и спрашиваю.

PHP
1
2
3
4
// проверка присутствует ли в массиве значение
if ( isset($array['page1']) ) {
    // ....
}

Добавлено через 1 минуту
вроде как когда я через индекс обращаюсь, там все равно поиск осуществляется перебором.

@nedel · 20.07.2015, 17:57

при такой длинне строки IndexOf должен быть быстрее
а если это реальная строка:

Сообщение от VLK

string dic = "abcdefghijklmnopqrstuvwxyz";

то лучше уж просто символ переводить в int беспосредсвенно

C#
1
2
3
 string dic = "abcdefghijklmnopqrstuvwxyz";
            char MyChar = 'c';
            int index = (int)MyChar - 97; //97 = (int)'a'

@XRoy · 20.07.2015, 18:18

VLK,
Сложность IndexOf - O(n)

В лучшем случае O(n) в худшем O(n^2)

C#
1
for (int i = 0; i < dic.Length; i++) collection.Add(dic[i], i);

Зато доступ к ключам словаря потом O(1)

@VLK · 20.07.2015, 18:22 **[ТС]**

XRoy, эммм.. я не так силен в математике, можно так на словах, что все же будет быстрее

Добавлено через 1 минуту
nedel, ну вообще строчка может быть дополнена любыми символами, по этому все же лучше так считать.

@XRoy · 20.07.2015, 18:32

VLK,
Когда количество запрсов в квадрате больше длины строки, то используйте словарь, иначе IndexOf

Более простыми словами, при большом количестве запросов к короткой строке нужен словарь, если длинная строка и малое количество запросов, то IndexOf

Следует учесть что это расчеты для худших случаев

@nedel · 20.07.2015, 18:33

Сообщение от VLK

строчка может быть дополнена любыми символами

если вдруг символы будут повторятся, то Dictionary не подойдет, так как ключ должен быть уникальным.

Сообщение от VLK

я не так силен в математике, можно так на словах, что все же будет быстрее

Dictionary, и чем больше элементов тем больше прирост производительности

Psilon · 20.07.2015, 18:51

VLK, что вы хотите-то в итоге от этой строки и символов? Глобально?

@VLK · 20.07.2015, 18:55 **[ТС]**

спасибо, подскажите еще такую вещь, Array.BinarySearch в данном случае может помочь, строка в которой надо будет осуществлять поиск, по длине будет ну где то:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcd efghijklmnopqrstuvwxyz

возможно минус буквы в верхнем регистре, возможно плюс какие то еще символы (штук 10-20)

запросов будет много.

Psilon · 20.07.2015, 19:00

VLK, да что нужно-то?

Если проверить, есть ли символ в таблице, это HashSet.
Если найти позицию в строке (причем работает конечно же только на сортированной) - можно BinarySearch'ем пройтись.
Если найти позицию в несортированной строке, то IndexOf.

и так далее.
Я понимаю, что после PHP это трудно, но стоит постараться думаю.

@VLK · 20.07.2015, 19:01 **[ТС]**

Psilon, сейчас ни какой конкретной задачи нет, когда то давно писал код для перебора разных комбинаций, что то типа подбора пароля, сейчас нашел этот код и решил переписать все "по уму", вот что написал:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static string GetNew(string Old, string dic = "0123456789") // 0123456789abcdefghijklmnopqrstuvwxyz
{
    char[] temp = Old.ToCharArray();
    for (int i = temp.Length - 1; i >= 0; i--)
    {
        if (temp[i] == dic[dic.Length - 1])
        {
            temp[i] = dic[0];
            continue;
        }
        else
        {
            int now = dic.IndexOf(temp[i]);
            temp[i] = dic[now + 1];
            break;
        }
    }
    return new string(temp);
}

я отправляю в метод строчку aba и словарь abcdefghijklmnopqrstuvwxyz, должен буду получить в ответ abb

Psilon · 20.07.2015, 19:04

VLK, а логика какая? код выше например ab0 даст.

@VLK · 20.07.2015, 19:11 **[ТС]**

Psilon, если передать словарь abcdefghijklmnopqrstuvwxyz и слово aba в результате я получу в ответ abb, как какая логика, допустим мне надо перебрать пароли, и я могу продолжить перебор с какого-нибудь конкретного места.

Добавлено через 1 минуту
я помню все это еще началось на форуме РНР, там какому то надо было перебирать пароли, некоторые стали писать, я тоже попробовал, но у меня получилась тонна кода и толком не работало, сейчас вот нашел, решил по новой сделать.
Ну и мало ли где то понадобиться еще.

Psilon · 20.07.2015, 19:17

VLK, ну тут тогда можно вообще на скорость забить, поиск на строке из 30 символов занимает 961 тактов на моем 3770k, учитывая частоту 3.4ГГц это 283 наносекунды. Что тут оптимизировать - непонятно.

@kolorotur · 21.07.2015, 12:17

Сообщение от VLK

как будет быстрее и производительнее?

Замерьте оба варианта в реалистичных условиях и сравните скорость.

@VLK · 21.07.2015, 12:59 **[ТС]**

Сообщение от kolorotur

Замерьте оба варианта в реалистичных условиях и сравните скорость.

я пытался, и какая то хрень вышла, ошибка, короче у меня в Dictionary первым элементом шел ноль (потом 1, 2,3 и т.д.) в виде символа (char), я отправляю символ ноль и и меня выкидывает ошибку, что в Dictionary нет символа ноль.

я забил, за тестировал Array.IndexOf и Array.BinarySearch все зависит от длинны, если словарь "0123456789", то быстрее IndexOf, а если "abcdefghijklmnopqrstuvwxyz" то уже быстрее BinarySearch, хотя разница там микро, короче я решил остановиться на IndexOf и все.

@kolorotur · 21.07.2015, 13:19

Сообщение от VLK

хотя разница там микро, короче я решил остановиться на IndexOf и все.

Правильное решение — при малых n O(n) = O(1), потому выбираем читаемость кода.
Если в будущем это место станет проблемой, то тогда уже можно будет и оптимизировать.

@VLK · 21.07.2015, 13:47 **[ТС]**

kolorotur, а где можно посмотреть вот эти формулы, только в короткой и понятной форме (статье), а то вы все их пишите, а я толком не догоняю что к чему.

@kolorotur · 21.07.2015, 14:42

Сообщение от VLK

а где можно посмотреть вот эти формулы

В смысле посмотреть про O-нотацию? На википедии статья для быстрого ознакомления есть.
Может, где-то проще расписано, не знаю.

Если вы про то, у какого алгоритма какая сложность в O, то просто гляньте соответствующий алгоритм на той же википедии — там будет справа табличка.
Почти для всех классов-коллекций в .NET документация указывает сложность добавления, поиска и удаления элемента.
Для своих алгоритмов сложность можете расчитать сами, тут где-то недавно была тема о том, как это делается.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@VLK 198 / 170 / 19 Регистрация: 05.05.2013 Сообщений: 1,236
	20.07.2015, 18:22 [ТС]
	XRoy, эммм.. я не так силен в математике, можно так на словах, что все же будет быстрее Добавлено через 1 минуту nedel, ну вообще строчка может быть дополнена любыми символами, по этому все же лучше так считать. 0

@XRoy 871 / 721 / 304 Регистрация: 15.04.2013 Сообщений: 2,047 Записей в блоге: 5
	20.07.2015, 18:32
	VLK, Когда количество запрсов в квадрате больше длины строки, то используйте словарь, иначе IndexOf Более простыми словами, при большом количестве запросов к короткой строке нужен словарь, если длинная строка и малое количество запросов, то IndexOf Следует учесть что это расчеты для худших случаев 1

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.07.2015, 18:51
	VLK, что вы хотите-то в итоге от этой строки и символов? Глобально? 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.07.2015, 19:00
	VLK, да что нужно-то? Если проверить, есть ли символ в таблице, это HashSet. Если найти позицию в строке (причем работает конечно же только на сортированной) - можно BinarySearch'ем пройтись. Если найти позицию в несортированной строке, то IndexOf. и так далее. Я понимаю, что после PHP это трудно, но стоит постараться думаю. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.07.2015, 19:04
	VLK, а логика какая? код выше например ab0 даст. 0

@VLK 198 / 170 / 19 Регистрация: 05.05.2013 Сообщений: 1,236
	20.07.2015, 19:11 [ТС]
	Psilon, если передать словарь abcdefghijklmnopqrstuvwxyz и слово aba в результате я получу в ответ abb, как какая логика, допустим мне надо перебрать пароли, и я могу продолжить перебор с какого-нибудь конкретного места. Добавлено через 1 минуту я помню все это еще началось на форуме РНР, там какому то надо было перебирать пароли, некоторые стали писать, я тоже попробовал, но у меня получилась тонна кода и толком не работало, сейчас вот нашел, решил по новой сделать. Ну и мало ли где то понадобиться еще. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.07.2015, 19:17
	VLK, ну тут тогда можно вообще на скорость забить, поиск на строке из 30 символов занимает 961 тактов на моем 3770k, учитывая частоту 3.4ГГц это 283 наносекунды. Что тут оптимизировать - непонятно. 2

@VLK 198 / 170 / 19 Регистрация: 05.05.2013 Сообщений: 1,236
	21.07.2015, 13:47 [ТС]
	kolorotur, а где можно посмотреть вот эти формулы, только в короткой и понятной форме (статье), а то вы все их пишите, а я толком не догоняю что к чему. 0