Добрый день! У меня вопрос возник в результате некоторых рассуждений, возможно,

он кривой и я чего-то не вижу, но все равно, буду рад любому фидбеку...

Допустим имеется некоторый метод:
bool isIni (std::string_view fileFormat) {
if (fileFormat == ".ini") {
return true;
}
return false;
}
Можно ли как-то ускорить факт осуществление проверки, например, делать это за константу?
Я не знаю, есть ли в плюсах такое, но почему бы для каждого модуля(метода класса/функции) не создать некую структуру(например, хеш-таблицу), которая будет содержать значения переданных аргументов в моменте выполнения, чтобы потом можно было оперировать ими быстрее?

Где-то вам все равно придется прочитать и сравнить строку за линейное время или в лучшем случае за log n

конкретно в этом случае захешировать переданный fileFormat, получить значение хеш-функции от ".ini" и потом просто сравнивать значение хешей? Ну ладно, пример не совсем удачный, но кажется есть случаи, при которых эта штука может сильно повлиять на производительность... Но я не уверен, можете как-то прокомментировать?!

Заведите enum со значениями формата, один раз прочитайте строковое представление и сохраните значение данного enum'а в зависимости от переданной строки

Как можно вообще сравнить две строки за константное время? Давай с этого начнем.

Не сильно повлияет. Тем более для хеширования нужно перебрать всю строку... И не забыть про коллизии.

Это не даст тебе О(1). Вопервых, если равны хэши, это ещё не значит, что равны хэшируемые значения. Мы только может сказать, что значения не равны, если хэши не равны. Во-вторых , угадай, какое же время вычисления хэша в зависимости от длины строки? О! Неожиданно! Это O(n) где n - длина строки!. А что же О(1) ? А не O(M) ? А это время поиска в хэш таблице с использованием хэш функции от строки, где M размер хэш-таблицы, число ключей в ней.

Коллизии тут ни при чем..

"Если равны хэши, это ещё не значит, что равны хэшируемые значения" Тебя же цитирую😁

Да, если это, то при чем, я только после про это подумал.

Я имел в виду что коллизии при поиске в хэш таблице только возникают, а тут его не будет.

Потому что проверка и так выполняется за О(1)

Лол, у тебя итак время константное, оно от fileFormat никак не зависит.

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

Так же у нас длина строки - константа, не?

согласен, просто меня интересовал именно факт проверки равности строк посимвольно, можно ли как-то асимптотику улучшить, пожертвовав немного памяти...

Шустрые реализации strcmp умеют сравнивать больше 1 символа за раз. Подойдёт?😆

В твоём утверждение прям есть ответ. Либо ты символы сравниваешь(подстроки) либо ранее полученные хэши. Из произведенных действий и складывается вычислительная сложность, как и оценка в О-нотации

Это называется питонячий @rlu_cache(None)

Думаю как и с сортировкой у сравнения строк есть теоретический минимум сложности и равен он O(n). Но доказательств я не читал

Может быть, я вас немного не понял, но кажется, вы вводите несуществующие понятия. Что по-вашему, означает "теоретический минимум сложности и равен он О(n)"?

То что лучше не сделать

А понял, только это не относится никак к big O notation-у...

У вас есть алгоритм сравнения строки с некоторым эталоном, его временная сложность O(n). Либо я не понял, что это за "это"

Он про time complexity. К примеру, для merge sort и для общего случая есть доказательство, что это не может быть лучше O(nlogn)

если использовать только попарные сравнения*

Нужно разделять computation model и time complexity. Это о разном. И первое зависит от второго. Для двух случайных строк time complexity будет Θ(n)

не понял значения computation model в вашем контексте, но о и тета это об одном и том же, просто разные неравенства