Форум программистов, компьютерный форум CyberForum.ru

Скорость выполнения. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Определить и вывести на экран количество слов во введеной строке http://www.cyberforum.ru/cpp-beginners/thread148662.html
определить и вывести на экран количество слов во введеной строке
C++ Упорядочить данный массив слов по алфавиту 1. Дана строка. Преобразовать ее, удалив каждый символ * и повторив каждый символ, отличный от *. 2. Упорядочить данный массив английских слов по алфавиту. 3. Дана строка, содержащая текст и некоторая буква. Подсчитать, сколько слов начинается с указанной буквы. Народ, помогите пожалста с кодом (dev c++) http://www.cyberforum.ru/cpp-beginners/thread148655.html
C++ Считывание и запись в файл
В Си. В файле data.txt даны квадратная матрица A и вектор X, соответствующих размерностей. Написать и протестировать функцию: а) Считывающую из файла матрицу A в двумерный массив, вектор X в одномерный б) Заменяющую чётные столбцы матрицы А на вектор Х в) Выводящую результирующую матрицу в файл out.txt. Б я знаю, А и В не могу...
C++ деление матриц
помогите пожалуйста выполнить деление матриц.
C++ Вычитание матриц http://www.cyberforum.ru/cpp-beginners/thread148638.html
помогите пожалуйста выполнить вычитание матриц.
C++ поворот многоугольника на плоскости Пдоскажите пожалуйста как сделать поворот многоугольника на плоскости или подскажите литературу где можно об этом почитать подробнее

Показать сообщение отдельно
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,343
23.06.2010, 13:26     Скорость выполнения.
У тебя алгоритмическая затыка. Сложность описанного алгорима O^2, а может быть, и O^3.... Тебе нужно не "сравнивать каждую с каждой" строчки, а:
1. читать из файла строчки,
2. тут же считать хеш строки (или ее "нужной" или "значащей" части),
3. хеши организовать в бинарное дерево или отсортированный массив, и по нему сразу же искать совпадения хешей. Если хеш не найден в таблице - добавить (ну и ссылки на строки где-то тут....). При выборе хорошей хеш-функции совпадение хешей == совпадение строк.
Вот где-то так. Это будет работать довольно шустро, сложность будет вряд ли сильно больше O. Конечно, возможны какие-то особенности описанного алгоритма, исходя из твоей конкретной задачи.

PS: если какие-то дохлые 70 тыс.строк считаются "огромным" файлом.... :-)) - развеселило.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru