Определение предельного значения объема данных при фиксированной верхней границе времени сортировки

@Pashk · Регистрация: 25.06.2018

Студворк — интернет-сервис помощи студентам

Мне нужно определить предельное значение объема данных при фиксированной границе времени сортировки, время ограничения равно 45с, а сортировка у меня шейкерная (Cocktail sort). Сделать это нужно в python с помощью timeit. Помогите пожалуйста, я не понимаю, как это делается, алгоритм взяла в интернете такой

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sample = [0, -1, 5, -2, 3]
 
left = 0
right = len(sample) - 1
 
while left <= right:
    for i in range(left, right, +1):
        if sample[i] > sample[i + 1]:
            sample[i], sample[i + 1] = sample[i + 1], sample[i]
    right -= 1
 
    for i in range(right, left, -1):
        if sample[i - 1] > sample[i]:
            sample[i], sample[i - 1] = sample[i - 1], sample[i]
    left += 1
 
print(sample)

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

@TAVulator · 08.12.2018, 08:42

Сообщение от Pashk

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

вот тест на 100 раз:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def f(sample = []): 
    left = 0
    right = len(sample) - 1
 
    while left <= right:
        for i in range(left, right, +1):
            if sample[i] > sample[i + 1]:
                sample[i], sample[i + 1] = sample[i + 1], sample[i]
        right -= 1
 
        for i in range(right, left, -1):
            if sample[i - 1] > sample[i]:
                sample[i], sample[i - 1] = sample[i - 1], sample[i]
        left += 1
    return sample
 
def g():
    sample = [0, -1, 5, -2, 3]
    print(f(sample))
 
import timeit
 
print(timeit.timeit(stmt=g, number=100))

вот результат:

Кликните здесь для просмотра всего текста

[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
[-2, -1, 0, 3, 5]
0.0013877239543944597

где 45с?

@Pashk · 08.12.2018, 15:41 **[ТС]**

Спасибо, начинаю понимать, но мне нужно найти не само время выполнение алгоритма, а количество данных, которое этот алгоритм сможет обработать за 45 секунд. Т.е. сколько должно быть символов в массиве, на сортировку которого потратится 45 сек. Пример приложила, но там пузырьковая сортировка, а мне нужно шейкерная и предельное время 45. НУжно видимо массив задать через random

@TAVulator · 08.12.2018, 21:08

вот как вариант прямого перебора (работает очень долго):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def f(sample = []): 
    left = 0
    right = len(sample) - 1
 
    while left <= right:
        for i in range(left, right, +1):
            if sample[i] > sample[i + 1]:
                sample[i], sample[i + 1] = sample[i + 1], sample[i]
        right -= 1
 
        for i in range(right, left, -1):
            if sample[i - 1] > sample[i]:
                sample[i], sample[i - 1] = sample[i - 1], sample[i]
        left += 1
    return sample
 
import timeit
import random
m = 3 # предел в секундах
s = 100 # шаг точности (на сколько элементов увеличивать при подгонке к требуемому времени, чем меньше, тем точнее
r = [1000, 1500, 2000, 2500, 5000, 5500, 10000, 20000, 30000, 40000, 50000]
x = 0
t = 0
while t <= m and x < len(r)-1:
    a = []
    for i in range(r[x]):
        a.append(random.randint(1,r[x]))
    st = timeit.default_timer()
    f(a)
    t = timeit.default_timer() - st
    print('for',r[x],'time is',t)
    if t > m:
        print('Find count elements for',m,'seconds with step in',s,'...')
        a = []
        for i in range(r[x-1]):
            a.append(random.randint(1,r[x]))
        st = timeit.default_timer()
        f(a)
        tt = timeit.default_timer() - st
        ii = 0
        for i in range(r[x-1],r[x],s):
            a = []
            for j in range(i):
                a.append(random.randint(1,i))
            st = timeit.default_timer()
            f(a)
            t = timeit.default_timer() - st
            print('for',i,'time is',t)
            if t > m:
                print(ii,'elements in',tt,'seconds')
                break
            else: 
                tt = t
                ii = i
    x +=1

Кликните здесь для просмотра всего текста

for 1000 time is 0.12808059714734554
for 1500 time is 0.32519173761829734
for 2000 time is 0.5004998468793929
for 2500 time is 0.8487902111373842
for 5000 time is 3.2625481230206788
Find count elements for 3 seconds with step in 100 ...
for 2500 time is 0.9424418550916016
for 2600 time is 0.8689425429329276
for 2700 time is 1.0171985500492156
for 2800 time is 1.0406807600520551
for 2900 time is 1.1865892391651869
for 3000 time is 1.1861676187254488
for 3100 time is 1.3566784160211682
for 3200 time is 1.5360220270231366
for 3300 time is 1.4325911598280072
for 3400 time is 1.539109985344112
for 3500 time is 1.6468648896552622
for 3600 time is 1.7937642228789628
for 3700 time is 2.1234793039038777
for 3800 time is 2.2553591770119965
for 3900 time is 2.0671570780687034
for 4000 time is 2.139128782786429
for 4100 time is 2.4807611098513007
for 4200 time is 2.4765074951574206
for 4300 time is 3.2518548388034105
4200 elements in 2.4765074951574206 seconds

@Pashk · 09.12.2018, 13:08 **[ТС]**

Спасибо огромное за помощь

Новые блоги и статьи Все статьи Все блоги /
Вывод данных через динамический список в справочнике Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .

@Pashk 0 / 0 / 0 Регистрация: 25.06.2018 Сообщений: 4
	08.12.2018, 15:41 [ТС]
	Спасибо, начинаю понимать, но мне нужно найти не само время выполнение алгоритма, а количество данных, которое этот алгоритм сможет обработать за 45 секунд. Т.е. сколько должно быть символов в массиве, на сортировку которого потратится 45 сек. Пример приложила, но там пузырьковая сортировка, а мне нужно шейкерная и предельное время 45. НУжно видимо массив задать через random Миниатюры Изображения 0

@Pashk 0 / 0 / 0 Регистрация: 25.06.2018 Сообщений: 4
	09.12.2018, 13:08 [ТС]
	Спасибо огромное за помощь 0

Определение предельного значения объема данных при фиксированной верхней границе времени сортировки

Решение