Здравствуйте, robin_of_the_wood, Вы писали:

___>>>Задачи разные бывают. Очень сильно разные. Пока создается впечатление что Вы кичитесь своим знанием математики и не очень в тему.
А>>Ну приведите мне программистскую задачу, нетребующую знания математики.
___>1. Почти весь саппорт и багфиксинг.

Как насчет багфиксинга с заменой наивной имплементации на нормальный алгоритм? Делал неоднократно.

Здравствуйте, monax, Вы писали:

M> А простая оптимизация с двоичными поиском и вставкой в массив пары (token, порядок_вставки) даст что-то около O(log n) + O(n). Второе слагаемое — это стоимость вставки в отсортированный массив.
N элементов по логарифму на каждый. Подумай ещё раз и умножь на N.

Здравствуйте, femidav, Вы писали:

А>>>Ну приведите мне программистскую задачу, нетребующую знания математики.
___>>1. Почти весь саппорт и багфиксинг.

F>Как насчет багфиксинга с заменой наивной имплементации на нормальный алгоритм? Делал неоднократно.
Ну я бы сказал что и среди такого багфаксинга не всегда есть куда математические знания приложить.
Иногда лишний раз ищем уже найденый элемент. Иногда не подумали что данных может быть много.
Иногда часто встречаемые комбинации данных можно обработать более оптимально.
При определенном желании все эти действия тоже можно свести к математике, но их в принципе может выполнить и человек матана не учивший.
Но конечто есть задачи где математика нужна и на уровне гораздо выше элементарного. Вот только в результате программирования в довольно разных направлениях мне все же не показалось, что таких задач большинство.
И именно поэтому я и сказал "Почти весь"
Хотя я то писал про свой опыт и вполне вероятно что в Вашей специализации положение дел несколько иное.

Здравствуйте, Антихрист, Вы писали:

А>Мое мнение — в стране нужно ввести жесткое лицензирование для программистов с требованиями по знаниям всех парадигм, 2-3 ЯП, и годного матана.

Тебе не страшно давать российской бюрократии право контролировать что либо? Российская бюрократия хоть что-то контролирует эффективно?

Здравствуйте, gandjustas, Вы писали:

M>>Как думаешь, что будет с этим кодом, если дать на вход пару миллионов элементов?
G>В случае с парой миллионов элементов этот код не имеет смысла если множество различных токенов не ограничено сверху. Ну получишь таким кодом (2*10^6 — 1) и что ты с ними дальше делать будешь?

обрабатывать буду. я взял это не с потолка, у меня есть задачи (немного, но есть), в которых приходится обрабатывать 1-1.5 млн уникальных объектов


M>>Эта задача вполне прикладного уровня, а у этого кода O(n^2).
G>А вот и нет. Потому что O(n^2) будет в худшем случае, когда множество различных токенов не ограничено сверху.

G>По сути почти всегда будет O(n*m), причем n не уменьшится, а m может оказаться достаточно мало, чтобы не было разницы как делать этот самый поиск.

А может и не оказаться. Хотя вот с O(n^2) я погорячился, рассматривал случай, когда множество не ограничено.

для примера, код из задачи перенесём в функцию:

def simple_insertion(tokeniter):
    tokens = []
    for token in tokeniter:
        if token not in tokens:
            tokens.append(token)
            
    return tokens

Потом нужен код, который проверит время работы в случаях: увеличиваю общее кол-во элементов, увеличиваю кол-во уникальных элементов, увеличиваю и то и другое на больших наборах (я буду работать с целыми числами, чтобы проще было)

from random import shuffle
from timeit import timeit

print 'n * 10 000'
counts = (100, 100)
for i in enumerate(counts):
    tokeniter = []
    for x in range(10000 * (i[0] + 1)):
        tokeniter += range(i[1])
    shuffle(tokeniter)
    
    setup = 'from __main__ import tokeniter, simple_insertion'
    print '%-10d:' % i[1], timeit('simple_insertion(tokeniter)', setup, number=1)


print 'n * 10 000'
counts = (100, 200)
for i in enumerate(counts):
    tokeniter = []
    for x in range(10000 / (i[0] + 1)):
        tokeniter += range(i[1])
    shuffle(tokeniter)
    
    setup = 'from __main__ import tokeniter, simple_insertion'
    print '%-10d:' % i[1], timeit('simple_insertion(tokeniter)', setup, number=1)
    
    
print 'n * 100'    
counts = (10000, 20000)
for count in counts:
    tokeniter = []
    for x in range(100):
        tokeniter += range(count)
    shuffle(tokeniter)
    
    setup = 'from __main__ import tokeniter, simple_insertion'
    print '%-10d:' % count, timeit('simple_insertion(tokeniter)', setup, number=1)

Вот результат работы

n * 10 000
100       : 1.21939106647
100       : 2.3543892777
n * 10 000
100       : 1.2208505149
200       : 2.32651335157
n * 100
10000     : 158.427437784
20000     : 673.992963291

Обрати внимание на последний результат. При больших объёмах данных поиск будет занимать длительное время.


G>В итоге ты заменил одно O(n) на другое O(n).
G>Но тебе повезло и ты ошибся. После binary search надо вставить элемент в позицию, найденную уже binary search, что приводит к общей сложности выполнения O(log n).

Тут ты тоже ошибся. В другом сообщении подсказывают, что будет O(n log n). Я бы вообще заменил на такое O(n)

def use_dict(tokeniter):
    tokens_dict = {}
    for token in tokeniter:
        if not tokens_dict.has_key(token):
            tokens_dict[token] = len(tokens_dict)
    tokens = range(len(tokens_dict))
    for token in tokens_dict:
        tokens[tokens_dict[token]] = token

    return tokens

Тогда на 10 000 и 20 000 получил бы
10000 : 0.00624857580812
20000 : 0.0121497736856

Здравствуйте, monax, Вы писали:

M>Здравствуйте, gandjustas, Вы писали:

M>>>Как думаешь, что будет с этим кодом, если дать на вход пару миллионов элементов?
G>>В случае с парой миллионов элементов этот код не имеет смысла если множество различных токенов не ограничено сверху. Ну получишь таким кодом (2*10^6 — 1) и что ты с ними дальше делать будешь?

M>обрабатывать буду. я взял это не с потолка, у меня есть задачи (немного, но есть), в которых приходится обрабатывать 1-1.5 млн уникальных объектов

Каким образом обрабатывать?

G>>В итоге ты заменил одно O(n) на другое O(n).
G>>Но тебе повезло и ты ошибся. После binary search надо вставить элемент в позицию, найденную уже binary search, что приводит к общей сложности выполнения O(log n).

M>Тут ты тоже ошибся. В другом сообщении подсказывают, что будет O(n log n).
Прочитай внимательно что я писал.

M>

M>def use_dict(tokeniter):
M>    tokens_dict = {}
M>    for token in tokeniter:
M>        if not tokens_dict.has_key(token):
M>            tokens_dict[token] = len(tokens_dict)
M>    tokens = range(len(tokens_dict))
M>    for token in tokens_dict:
M>        tokens[tokens_dict[token]] = token

M>    return tokens
M>

M>Тогда на 10 000 и 20 000 получил бы
M>10000 : 0.00624857580812
M>20000 : 0.0121497736856

Ты еще не понял что в стандартной библиотеке C# есть функция distinct, которая делает то что нужно, быстро и не требует знания алгоритмов?

Здравствуйте, gandjustas, Вы писали:

M>>Всё это прикладной уровень, но без знания алгоритмов твоя программа будет работать по коду из задачи, что приведёт к потере машинного времени, да и результата ты можешь не дождаться несколько дней.
G>Да-да-да...
G>1)Вставка и поиск в массиве: 2 минуты
G>2)Поиск в отсортированном массиве: 4 секунды
G>3)tokeniter.Distinct(): 0.3 секунды

Сравнение с Distinct некорректно, т.к. Distinct теряет порядок следования элементов.

Здравствуйте, gandjustas, Вы писали:

G>Ты еще не понял что в стандартной библиотеке C# есть функция distinct, которая делает то что нужно, быстро и не требует знания алгоритмов?

ты ещё не понял, что distinct делает не то, что нужно в задаче?

Здравствуйте, Lloyd, Вы писали:

L>Сравнение с Distinct некорректно, т.к. Distinct теряет порядок следования элементов.
Как это теряет? Судя по коду, ничего он не теряет.

Здравствуйте, MxMsk, Вы писали:

L>>Сравнение с Distinct некорректно, т.к. Distinct теряет порядок следования элементов.
MM>Как это теряет? Судя по коду, ничего он не теряет.

был не прав, когда писал. правильнее "не гарантирует".

Здравствуйте, Lloyd, Вы писали:

L>был не прав, когда писал. правильнее "не гарантирует".
В оригинале:

The result sequence is unordered.

Думаю то, что не применяется никакого упорядочивания не означает, что исходный порядок нарушается. Может есть какие-то уточнения?

Здравствуйте, MxMsk, Вы писали:

L>>был не прав, когда писал. правильнее "не гарантирует".
MM>В оригинале:
MM>

MM>The result sequence is unordered.

MM>Думаю то, что не применяется никакого упорядочивания не означает, что исходный порядок нарушается. Может есть какие-то уточнения?

Это так же означает, что не гарантируется, что порядок сохраняется, если не сказано иного.
На самом деле, ты прав, по исходнику видно, что действительно порядок сохраняется.

Здравствуйте, Lloyd, Вы писали:

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

Здравствуйте, monax, Вы писали:

M>Эта задача вполне прикладного уровня, а у этого кода O(n^2). Как думаешь, что будет с этим кодом, если дать на вход пару миллионов элементов? А простая оптимизация с двоичными поиском и вставкой в массив пары (token, порядок_вставки) даст что-то около O(log n) + O(n). Второе слагаемое — это стоимость вставки в отсортированный массив.

а зачем вставка в отсортированный массив? Есть же карты, основанные на rbtree, которые вполне себе O(log n) на вставку, поиск и удаление..

Здравствуйте, Libsdebs, Вы писали:

L>а зачем вставка в отсортированный массив? Есть же карты, основанные на rbtree, которые вполне себе O(log n) на вставку, поиск и удаление..

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

Здравствуйте, monax, Вы писали:

L>>а зачем вставка в отсортированный массив? Есть же карты, основанные на rbtree, которые вполне себе O(log n) на вставку, поиск и удаление..
M>там в описании задачи просто есть пункт, что результирующий список содержит элементы в порядке их появления, поэтому я и не стал брать бинарное дерево. собственно и "порядок вставки" я хранил, чтобы развернуть его в необходимом порядке.

ищем в карте(множество), если нет такого, то вставляем и в карту, и в массив. если элемент данных имеет большой размер, то в массив вставляем ссылку на элемент в карте.

Здравствуйте, Libsdebs, Вы писали:

L>ищем в карте(множество), если нет такого, то вставляем и в карту, и в массив. если элемент данных имеет большой размер, то в массив вставляем ссылку на элемент в карте.

карта — это HashMap? если да, то подобное решение я и предложил выше:

def use_dict(tokeniter):
    tokens_dict = {}
    for token in tokeniter:
        if not tokens_dict.has_key(token):
            tokens_dict[token] = len(tokens_dict)
    tokens = range(len(tokens_dict))
    for token in tokens_dict:
        tokens[tokens_dict[token]] = token

    return tokens

здесь {} — это создание ассоциативного массива, в котором объекты выступают в качестве ключей. размер элемента данных значения не имеет, потому что в питоне операция a = b копирует ссылку, а не создаёт копию обьекта.

Здравствуйте, monax, Вы писали:

L>>ищем в карте(множество), если нет такого, то вставляем и в карту, и в массив. если элемент данных имеет большой размер, то в массив вставляем ссылку на элемент в карте.
M>карта — это HashMap? если да, то подобное решение я и предложил выше:

карта — это карта. которая согласно википедии часто реализуется через "hash table", либо "self-balancing binary search tree "
http://en.wikipedia.org/wiki/Associative_array
То что вы использовали в новом варианте называется python dictionary, что можно назвать картой.

Кстати о сабже, то есть признаёте, что первоначально предложили левый алгоритм с "плохой" сложностью?

Здравствуйте, Libsdebs, Вы писали:

L>Кстати о сабже, то есть признаёте, что первоначально предложили левый алгоритм с "плохой" сложностью?

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

def use_bin_search(tokeniter):
    def __insert(tokens_list, item):
        first = 0
        length = len(tokens_list)
        last = length

        if last == 0:
            tokens_list.append((item, length ))
        elif tokens_list[0][0] > item:
            tokens_list.insert(0, (item, length))
        elif tokens_list[last - 1][0] < item:
            tokens_list.append((item, length))
        else:
            while first < last:
                middle = (first + last) / 2
                if item <= tokens_list[middle][0]:
                    last = middle
                else:
                    first = middle + 1

            if tokens_list[last][0] != item:
                tokens_list.insert(last, (item, length))
            
    tokens = []
    for token in tokeniter:
        __insert(tokens, token)

    tokens_dict = {}
    for t in tokens:
        tokens_dict[t[1]] = t[0]
    
    tokens = [tokens_dict[k] for k in sorted(tokens_dict)]
    
    return tokens

Здравствуйте, Антихрист, Вы писали:

А>Наболело.
А>Девелоперы. Которые так и сыплют абревиатурами и лейбами NET, J2EE, LINQ, ASP, JSP, Hibarnate, Spring, наизусть знают ООП паттерны. Млеют от того насколько они круто развернут за день распределенную высоконагруженную систему.

А>А смотришь на их результат — интерфейсы все как один говно, система тормозит от этих ваших гибернейтов нещадно (кстати, до сих пор не понимаю как эта жирная, убогая ОРМ может помочь при разработке хоть большой, хоть малой ИС). За код который они пишут, у нас в команде убивают без суда и следствия.

А я устал от "хардкорных" сишников, кричащих, что их окно с меню из 3х пунктов запускается моментально и занимает на диске 23 килобайта. При этом, абсолютно неспособных написать приложение для бухгалтера из 30 типов форм и 30 таблиц и десятка отчетов, в условиях постоянно меняющихся требований. Да еще чтобы оно не текло. Да еще, чтобы после изменений релиз можно было выкатывать на следующий день.

Если же оно впервые в жизни ими пишется, часто открывается понимание, что "тот велосипед который от которого я так торчал всю прошлую неделю и юзаю теперь повсеместно, оказывается называется фабричный метод", а исправляя в сотый раз косяки самоконструируемого SQL приходится с завистью поглядывать на джавистов с их Hibernate. А когда приложение через 3 года вырастет до 45!!! типов формочек — придет осознание, что надо все нафик выкинуть и переписать на java или .net. Фиг с ними с тормозами, оно по крайней мере сможет работать не падая и добавление очередной формы не будет превращаться в месячный НИОКР. А робкий вопрос бухгалтера: "мне бы вот тут галочку, чтобы можно было переключать вывод людей и гвоздей", перестанет делать из программиста рычащее животное. Вот тогда этот сишник за пару месяцев освоит NET, J2EE, LINQ, ASP, JSP, Hibernate, Spring ибо будет понимать, что это, какую задачу решает и почему сделано именно так.