from itertools import groupby
from timeit import timeit
import random
def inplace(d):
m_d = [[x,0] for x in d]
mark = 0
_ = iter(range(len(m_d)-1))
for i in _:
while (m_d[i+1][0]-m_d[i][0] <2) and (i<len(m_d)-2):
m_d[i][1] = mark
next(_)
i+=1
m_d[i][1] = mark
mark +=1
# проверка на то, что последние элемент входит в маркируемый блок
if m_d[len(m_d)-1][0] - m_d[len(m_d)-2][0] <2:
m_d[len(m_d)-1][1] = m_d[len(m_d)-2][1]
return m_d
def markgroups(elems):
def getkey(idx):
"По номеру элемента возвращает ключ его группы"
return elems[idx] - idx
groups = (group
for _, group in groupby(range(len(elems)), key=getkey))
return [[elems[idx], group_idx]
for group_idx, group in enumerate(groups)
for idx in group]
data = [x for x in range(1000000) if random.random() < 0.8]
print('inplace: {:.4f} s'.format(
timeit('inplace(data)',
setup='from __main__ import inplace, data',
number=1)))
print('markgroups: {:.4f} s'.format(
timeit('markgroups(data)',
setup='from __main__ import markgroups, data',
number=1)))
a = inplace(data)
b = markgroups(data)
assert a == b, "Результаты различаются"
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGdyb3VwYnkKZnJvbSB0aW1laXQgaW1wb3J0IHRpbWVpdAppbXBvcnQgcmFuZG9tCgoKZGVmIGlucGxhY2UoZCk6CiAgICBtX2QgPSBbW3gsMF0gZm9yIHggaW4gZF0KCiAgICBtYXJrID0gMAogICAgXyA9IGl0ZXIocmFuZ2UobGVuKG1fZCktMSkpCiAgICBmb3IgaSBpbiBfOgogICAgICAgIHdoaWxlIChtX2RbaSsxXVswXS1tX2RbaV1bMF0gPDIpIGFuZCAoaTxsZW4obV9kKS0yKToKICAgICAgICAgICAgbV9kW2ldWzFdID0gbWFyawogICAgICAgICAgICBuZXh0KF8pCiAgICAgICAgICAgIGkrPTEKICAgICAgICBtX2RbaV1bMV0gPSBtYXJrCiAgICAgICAgbWFyayArPTEKICAgICMgINC/0YDQvtCy0LXRgNC60LAg0L3QsCDRgtC+LCDRh9GC0L4g0L/QvtGB0LvQtdC00L3QuNC1INGN0LvQtdC80LXQvdGCINCy0YXQvtC00LjRgiDQsiDQvNCw0YDQutC40YDRg9C10LzRi9C5INCx0LvQvtC6CiAgICBpZiBtX2RbbGVuKG1fZCktMV1bMF0gLSBtX2RbbGVuKG1fZCktMl1bMF0gPDI6CiAgICAgICAgbV9kW2xlbihtX2QpLTFdWzFdID0gbV9kW2xlbihtX2QpLTJdWzFdCiAgICByZXR1cm4gbV9kCgoKZGVmIG1hcmtncm91cHMoZWxlbXMpOgogICAgZGVmIGdldGtleShpZHgpOgogICAgICAgICLQn9C+INC90L7QvNC10YDRgyDRjdC70LXQvNC10L3RgtCwINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINC60LvRjtGHINC10LPQviDQs9GA0YPQv9C/0YsiCiAgICAgICAgcmV0dXJuIGVsZW1zW2lkeF0gLSBpZHgKCiAgICBncm91cHMgPSAoZ3JvdXAKICAgICAgICAgICAgICBmb3IgXywgZ3JvdXAgaW4gZ3JvdXBieShyYW5nZShsZW4oZWxlbXMpKSwga2V5PWdldGtleSkpCgogICAgcmV0dXJuIFtbZWxlbXNbaWR4XSwgZ3JvdXBfaWR4XQogICAgICAgICAgICBmb3IgZ3JvdXBfaWR4LCBncm91cCBpbiBlbnVtZXJhdGUoZ3JvdXBzKQogICAgICAgICAgICBmb3IgaWR4IGluIGdyb3VwXQoKCmRhdGEgPSBbeCBmb3IgeCBpbiByYW5nZSgxMDAwMDAwKSBpZiByYW5kb20ucmFuZG9tKCkgPCAwLjhdCgoKcHJpbnQoJ2lucGxhY2U6ICAgIHs6LjRmfSBzJy5mb3JtYXQoCiAgICB0aW1laXQoJ2lucGxhY2UoZGF0YSknLAogICAgICAgICAgIHNldHVwPSdmcm9tIF9fbWFpbl9fIGltcG9ydCBpbnBsYWNlLCBkYXRhJywKICAgICAgICAgICBudW1iZXI9MSkpKQpwcmludCgnbWFya2dyb3VwczogezouNGZ9IHMnLmZvcm1hdCgKICAgIHRpbWVpdCgnbWFya2dyb3VwcyhkYXRhKScsCiAgICAgICAgICAgc2V0dXA9J2Zyb20gX19tYWluX18gaW1wb3J0IG1hcmtncm91cHMsIGRhdGEnLAogICAgICAgICAgIG51bWJlcj0xKSkpCgphID0gaW5wbGFjZShkYXRhKQpiID0gbWFya2dyb3VwcyhkYXRhKQoKYXNzZXJ0IGEgPT0gYiwgItCg0LXQt9GD0LvRjNGC0LDRgtGLINGA0LDQt9C70LjRh9Cw0Y7RgtGB0Y8i