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

@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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@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

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

Решение