2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как оптимизировать алгоритмы со скоростью O(1)
Сообщение08.12.2010, 08:49 
Заслуженный участник


08/04/08
8562
Как оптимизировать алгоритмы со скоростью O(1)?
Подробнее: насколько важно объявлять более легкие по числу байт переменные, насколько важно уменьшение числа if-ов, насколько утяжеляет программу объявление отдельных процедур и функций, новых типов переменных и т.п.. От чего следует избавляться в первую очередь?
(интересуют языки Delphi, C++, PL/SQL, если ответ будет сильно от языка зависеть)
Литература приветствуется

 Профиль  
                  
 
 Re: Как оптимизировать алгоритмы со скоростью O(1)
Сообщение10.12.2010, 06:57 
Заслуженный участник


08/04/08
8562
Вообще вопрос понятен? М.б. какие-то простейшие фрагменты кода привести?

 Профиль  
                  
 
 Re: Как оптимизировать алгоритмы со скоростью O(1)
Сообщение10.12.2010, 17:15 
Аватара пользователя


31/10/08
1244
Ну вроде все известно. Читаешь про оптимизацию.
Компиляторы которые компилируют в родной код машины(Delphi, C++) следует оптимизировать под машину.
http://wasm.ru/publist.php?list=10
В оригинале лучше читать
http://www.intel.com/Assets/PDF/manual/248966.pdf

Еще книга дракона (Альфред Ахо,Рави Сети,Джеффри Ульман Компиляторы). Советую читать 3 издание оно полнее в этом вопросе.

Если пишите под ARM то тут надо читать под конкретную разновидность процессора.
Под CUDA свои тонкости.

PL/SQL свои особенности
Тут тоже книги есть.

Универсальные правила такие.
0. Найти оптимальный алгоритм.

1. Основное правило выигрываешь в скорости проигрываешь в памяти и наоборот.
Это в первую очередь касается баз данных. Данные надо дублировать для быстрого доступа. Да это противоречит 3 форме. Но зато работает на практике. Правда там очень тонкая грань.


2. Уменьшение операций чтения и записи в память.

3. Кэширование данных. Создания кэша (чаще всего используется). Разбиение данных так чтобы они помещались в кэш. Тут помогают блочные алгоритмы.

А потом уже играются с If-ами, они много отъедают.

 Профиль  
                  
 
 Re: Как оптимизировать алгоритмы со скоростью O(1)
Сообщение11.12.2010, 09:27 
Заслуженный участник


08/04/08
8562
Ага! Мне в общем тогда понятно. Это уже почти метод. Я его запомню.
Блин, жаль литература на английском, боюсь, у меня нет столько времени.
Сейчас требований к памяти вроде как нет (только исключая создание таблиц и индексов), т.е. будем если что в пользу скорости все делать.
И я пишу на высоком уровне прикладные частные вещи - т.е. делать кэширование не мне. Уменьшать число операций чтения и записи - это мне! Если доберусь до if-ов

Давайте я тогда буду сюда периодически писать примитивные вопросы, а Вы мне будете отвечать, надеюсь, Вам будет не лень.
1. PL/SQL. Имеется пакет для участника, в нем есть method write, который, исключая некоторые мелочи, выглядит так:
Код:
if b then
  insert into TABLE(FIELD1, ..., FIELDn)
  values (V1,...Vn);
else
  update TABLE
  set
    FIELD1 = V1,
    ....
    FIELDn = Vn
where ID = nID;
end if;

Вот про update. Зачастую реально обновляются не все поля, а только их малая часть. Значит для более быстрой работы кода нужно писать update только тех полей, которые могли обновиться. Но тогда получится, что надо не method write вызывать, а каждый раз писать update отдельно и исправлять каждый раз в случае необходимости тоже отдельно (тут я немного ушел в тему topic39396.html). Как в этом случае быть?

-- Сб дек 11, 2010 12:37:05 --

И еще вопрос сразу, пока вспомнил:
2. Как быстрее работает в PL/SQL: select into с обработкой exception-а when NO_DATA_FOUND, или же select count(*) into iCnt, и в случае if iCnt>0 выполнять select into уже без exception?
(если непонятно - могу подробнее написать, просто букоф будет много)

 Профиль  
                  
 
 Re: Как оптимизировать алгоритмы со скоростью O(1)
Сообщение11.12.2010, 13:28 
Аватара пользователя


31/10/08
1244
Sonic86
С PL/SQL я мало знаком. Поэтому не смогу помочь.
Цитата:
select count(*) into iCnt, и в случае if iCnt>0 выполнять select into уже без exception?

Тут у тебя 2 Select, а это означает полный проход по таблице 2 раза! Ясно что первый вариант быстрее будет. Exception у тебя проверится всего 1 раз и то, то по окончанию select

 Профиль  
                  
 
 Re: Как оптимизировать алгоритмы со скоростью O(1)
Сообщение11.12.2010, 13:36 
Заслуженный участник


08/04/08
8562
Pavia писал(а):
С PL/SQL я мало знаком. Поэтому не смогу помочь.

Жаль. Но вообще-то там достаточно знать что такое update. Просто не смог кратко написать. Если будут проще вопросы - спрошу
Pavia писал(а):
Тут у тебя 2 Select, а это означает полный проход по таблице 2 раза! Ясно что первый вариант быстрее будет. Exception у тебя проверится всего 1 раз и то, то по окончанию select

То есть Вы считаете, что exception обрабатывается быстрее, чем select :roll: Значит придется код рефакторить...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group