DjangoBB LoFi version

Найти - Пользователи

Полная версия: сокращение последовательности в строке, re

Начало » Центр помощи » сокращение последовательности в строке, re

1 2 3 4 5 6 7

py.user.next

Окт. 29, 2013 23:11:12

Budulianin
Какой там код? Тесты на бумаге пишутся, а потом значение в ассерты подставляются, для сравнения

ты меня удивляешь всё больше и больше
ну, отскань бумагу, пришли картинку, поугараем

Budulianin

Окт. 29, 2013 23:12:22

py.user.next
ты меня удивляешь всё больше и больше
ну, отскань бумагу, пришли картинку, поугараем

Что смешного?

Если не знаешь, как это делается, иди читай Майерса, Канера и потом сам над собой посмейся

bismigalis

Окт. 30, 2013 09:31:28

py.user.next
смотри замеры

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

py.user.next

Окт. 30, 2013 14:18:12

bismigalis
я не про скорость, а про миллиард элементов

скорость одна и та же, это о чём говорит ?
обновлено

bismigalis

Окт. 30, 2013 16:52:21

py.user.next
это о чём говорит ?

это ничего не говорит о потребляемой памяти

Lexander

Окт. 30, 2013 20:16:43

bismigalis
Список из миллиарда целых чисел - это чуть меньше 16ГБ памяти на 32-х битной системе.
64ГБ - не самый большой объем RAM нужно установить на машину как для задачи, в которой фигурируют такие данные, чтобы все манипуляции производились только в памяти :)
Это с точки зрения инженерного решения невыдуманной и неучебной задачи.
Иначе нужно еще раньше подумать о сортировке такого кол-ва элементов ;)

Но в целом, конечно, вы правы. Копирование, а оно есть в обоих вариантах, таких объемов увеличит получаемые тайминги.
Но, все равно они, имхо, останутся сравнимыми.

py.user.next
скорость одна и та же, это о чём говорит ?

Только о том, что над конечной копией выполняются почти одни и те же операции.
В обоих случаях создается объект slice, который остается на вершине стэка (inplace операция, вызова функций нет).
В одном случае итереатор создается явно в islice (здесь же создается сам slice).
Во втором случае итератор создается неявно с помощью конструкции for x in slice.
Итератор содержит ссылку на итерируемый объект, но не копирует дополнительно его внутри.

Сами списки хранятся как массивы (если речь о Cython). Обращение к отдельным элементам - быстрое. Даже копирование - быстрое.

В итоге - одинаковая скорость.

py.user.next

Окт. 30, 2013 21:29:29

Lexander
Список из миллиарда целых чисел - это чуть меньше 16ГБ памяти на 32-х битной системе.

>>> 1000000000 * 4 / 1048576 / 1024
3.725290298461914
>>>

3.7GiB - сами числа

Lexander
Только о том, что над конечной копией выполняются почти одни и те же операции.

во-во, а если итератор даёт одно время и срез даёт это же время, то никакой разницы нет, потому что происходит одно и то же

bismigalis
это ничего не говорит о потребляемой памяти

так ты и не уменьшишь потребление
список используется потому, что нужна сортировка (в идеале, конечно, нужно подать итератор и выдать итератор), но у итераторов нет метода .sort(), а функция sorted() возвращает список (потому что элементы читаются и переставляются)

то есть это особой скорости не даст

а стоит ли делать yield вместо списка вывода ? можно сделать, а можно и не делать, всё равно при дальнейшем использовании он будет весь читаться
там преимущество, походу, только в плане параллельности (то есть, можно прочитать полгенератора, потом делать что-то другое, а потом прочитать ещё полгенератора)

Lexander
Итератор содержит ссылку на итерируемый объект, но не копирует дополнительно его внутри.

ну, по идее-то, срез должен сначала создать копию части списка, а потом для неё выполнить iter(), а itertools.islice() просто должен взять первый элемент и проверить для него условия, переданные при создании итератора (а iter() как бы вообще ничего не делает, потому itertools.islice() просто self возвращает)

Lexander

Окт. 30, 2013 23:35:13

py.user.next
3.7GiB - сами числа

В Питоне все - объекты. Уже исходя из этого будет больше. ;)
Используйте getsizeof() и получите очень интересные результаты.

Если я правильно помню, на 32 битах int в Питоне занимает 12 байт.
Для 10^9 только числа займут почти 12 ГБ.
Плюс, грубо берем - треть, накладные расходы на список для GC - около 4 ГБ.
Такие дела.

PS
Кстати, я тут подумал, разница может быть и более существенная. Зависит от параметров среза.
Например, чем дальше начало среза, тем дольше будет выполняться islice.

bismigalis

Окт. 31, 2013 13:46:46

вообще миллиард элементов это много, мало компьютеров поместят это в памяти
давайте говорить про миллион элементов
поставил эту штуку https://pypi.python.org/pypi/memory_profiler/0.30
на вход подаю range(10**6) #python2

версия py.user.next

Line #    Mem usage    Increment   Line Contents
================================================
     3     39.9 MiB      0.0 MiB   @profile 
     4                             def convert_any_order(lst):
     5     39.9 MiB      0.0 MiB       fmt = '{}:{}'
     6     39.9 MiB      0.0 MiB       lst.sort()
     7     39.9 MiB      0.0 MiB       out = []
     8     39.9 MiB      0.0 MiB       prev, inrange, first = lst[0], False, 0
     9     47.5 MiB      7.6 MiB       for x in lst[1:]:
    10     47.5 MiB      0.0 MiB           if prev + 1 != x:
    11                                         if inrange:
    12                                             inrange = False
    13                                             out.append(fmt.format(first, prev))
    14                                         else:
    15                                             out.append(str(prev))
    16     47.5 MiB      0.0 MiB           elif not inrange:
    17     47.5 MiB      0.0 MiB               inrange, first = True, prev
    18     47.5 MiB      0.0 MiB           prev = x
    19     39.9 MiB     -7.6 MiB       if inrange:
    20     39.9 MiB      0.0 MiB           out.append(fmt.format(first, prev))
    21                                 else:
    22                                     out.append(str(prev))
    23     39.9 MiB      0.0 MiB       return out

в моей же первой версии всё плохо :)

Line #    Mem usage    Increment   Line Contents
================================================
     3     39.8 MiB      0.0 MiB   @profile
     4                             def f(lst):
     5     39.9 MiB      0.0 MiB       lst.sort()
     6     39.9 MiB      0.0 MiB       res = []
     7     39.9 MiB      0.0 MiB       tmp = []
     8    126.0 MiB     86.1 MiB       for item, nextitem in zip(lst, lst[1:]+[None]):
     9    126.0 MiB      0.0 MiB           tmp.append(item)
    10    126.0 MiB      0.0 MiB           if nextitem is None or nextitem - item != 1:
    11    126.0 MiB      0.0 MiB               if len(tmp) > 1:
    12    126.0 MiB      0.0 MiB                   res.append(tmp)
    13                                         else:
    14                                             res.extend(tmp)
    15    126.0 MiB      0.0 MiB               tmp = []
    16                             
    17    126.0 MiB      0.0 MiB       out = []
    18    126.0 MiB      0.0 MiB       for item in res:
    19    126.0 MiB      0.0 MiB           if isinstance(item, list):
    20    126.0 MiB      0.0 MiB               out.append("{}:{}".format(item[0], item[-1]))
    21                                     else:
    22                                         out.append(str(item))
    23    126.0 MiB      0.0 MiB       print ', '.join(out)

bismigalis

Окт. 31, 2013 13:50:33

короче

for x in lst[1:]:

не дает удвоения как я думал