DjangoBB LoFi version

Полная версия: Кейса нет..... какая альтернатива

Начало » Python для новичков » Кейса нет..... какая альтернатива

1 2 3 4

doza_and

Окт. 26, 2013 08:59:13

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

import time
import numpy as np
import pylab
n = []
t = []
f=4
rs=np.random.rand(50)
while f < 1000000:
    i=int(f)
    val = set(np.random.rand(i))
    t0 = time.clock()
    ou1= [j in val for j in rs]
    t1 = time.clock()
    n.append(len(val))
    t.append(t1-t0)
    print n[-1], t[-1]
    f*=1.2
pylab.plot(n,t);pylab.show()

на
python 2.75 winxp32
4 3.54635463546e-05
4 3.47914791479e-05
5 3.41404140414e-05
6 3.3303330333e-05
8 3.29192919292e-05
7054 3.87518751875e-05
8465 3.71497149715e-05
10159 4.30603060306e-05
12190 4.29252925293e-05
14629 4.05670567057e-05
17554 4.01740174017e-05
324561 8.08100810081e-05
389474 8.11731173118e-05
467368 7.93249324933e-05
560842 8.10831083102e-05
673011 8.52385238526e-05

Моя художественная интерпретация:
Алгоритм с константным временем поиска. Но на больших объемах начинает сказываться выпадание из кэша.

Возвращаясь к теме
Что лучше

switch(i)
{
 case 1:{f1(); break}
 case 20:{f20(); break}
.....
}

или

set<int,void *f()> arr;
arr[i]()

Рассмотрение получившихся ассемблерных кодов показало, что большинство компиляторов сваливается на банальный последовательный перебор i==1,i==20,… с джампами на соответствующий кусок кода. Иногда встречается двоичный поиск. Выравнивания блоков кода и вычисления адреса перехода ни разу не встретил :(

Isem

Фев. 25, 2014 17:33:46

doza_and
Рассмотрение получившихся ассемблерных кодов показало, что большинство компиляторов сваливается на банальный последовательный перебор i==1,i==20,… с джампами на соответствующий кусок кода. Иногда встречается двоичный поиск. Выравнивания блоков кода и вычисления адреса перехода ни разу не встретил :(

Сейчас уже, начиная с Watcom c++, который, к сожалению, микрософт загубил на корню, кейс легко оптимизируется. Только дебил выпустит компилятор, типа делфи, и будут рады. Питон ими даже не пахнет.

Lexander

Фев. 25, 2014 17:44:28

Isem
Каким способом решается проблема ложных предсказаний и ветвлений в алгоритме оптимизации case?
Уточняю для остальных: я о CPU.

Isem

Фев. 25, 2014 17:56:40

Вы специалист по ассемблеру и устройству CPU? Давайте разделим: Питон, программирование вообще, программная модель процессора и электроника. Во всех этих случаях оптимизация case совершенно разная. В каждом случае надо включать мозг и находить свое решение, и не одно.

PanovSergey

Фев. 25, 2014 19:29:09

Я стесняюсь спросить а зачем оптимизировать то что оптимизироваться нет смысла? Ведь ТС совсем не об этом спрашивал..

sergeek

Фев. 25, 2014 21:12:28

doza_and

    t0 = time.clock()
    ou1= [j in val for j in rs]
    t1 = time.clock()

У меня time.clock какую-то НЁХ возвращает. С time.time вполне константное время

Lexander

Фев. 25, 2014 22:30:34

PanovSergey
Я стесняюсь спросить а зачем оптимизировать то что оптимизироваться нет смысла? Ведь ТС совсем не об этом спрашивал..

Вы правы.
И не стесняйтесь

Мы, в порядке оффтопа, ушли в сторону.
Точнее, углубились в тему.

Isem
Я уже давно не занимаюсь ассемблером.
Т.к. тема мне интересна и есть определенные знания в ней, ваше упоминание оптимизации, да еще легкой, вызвало вопрос о способе решения древней (со времен Пентиума) проблемы.

doza_and вон правильно написал: оптимизация местами встречается, но она в сфере оптимизации работы с кеш, шириной шины и общих алгоритмов.
В этом нет ничего нового.

У вас есть конкретный ответ по озвученной проблеме?

doza_and

Фев. 26, 2014 18:53:50

sergeek
У меня time.clock какую-то НЁХ возвращает

???
Давайте посмотрим полный код вашего скрипта.
Вот у меня так:

>>> import time
>>> time.clock()
5.91061322612221e-07

Под разными операционными системами clock несколько по разному работает.

PanovSergey
а зачем оптимизировать то что оптимизироваться нет смысла?

Да для ТС это не существенно. А вот под с или с++ я довольно часто встречал диспетчеризацию сообщений в виде switch на несколько сотен, а то и тысяч пунктов. Если посмотреть выход bizon+flex то конечный автомат перехода между состояниями парсера тоже часто реализован в виде switch. А это основа многих комплияторов. Не самая главная, но существенная…

sergeek

Фев. 26, 2014 19:34:04

doza_and
Давайте посмотрим полный код вашего скрипта.

я просто заменил в вашем time.clock на time.time

doza_and
Вот у меня так

>>> import time
>>> time.clock()
0.02
>>> time.clock()
0.02

py.user.next

Фев. 26, 2014 20:19:44

doza_and
А вот под с или с++ я довольно часто встречал диспетчеризацию сообщений в виде switch на несколько сотен, а то и тысяч пунктов.

это где это ?
обычно в таблицу заносится, по которой потом происходит маленькое переключение;
оно и читаемее