Можно ли ускорить выполнение программы?

@wer1 · Регистрация: 05.07.2018

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

Задача
1. дан файл 1.txt, содержащий список русских слов (размеры файла порядка 1 МБ)
2. требуется отсортировать этот файл в алфавитном порядке.
Решение
1. величина файла такова, что его не удастся поместить в массив и потом этот массив
сортировать обычным способом. Придется сортировать сам файл 1.txt
2. изначально открываем этот файл и считаем сколько он содержит слов. (число слов
равно числу строк)
3. далее будет выполняться следующий алгоритм

3.0 задаем цикл FOR i = 1 TO N
3.1 открываем файл 1.txt для чтения
3.2 открываем файл 2.txt для добавления записи в конец файла
3.3 считываем первое слово из файла 1.txt
3.4 задаем цикл DO - LOOP UNTIL EOF(1)
3.5 считываем второе слово из файла 1.txt
3.6 сравниваем первое слово со вторым
3.7 меньшее из этих слов будет записано в файл 2.txt
3.8 а большее слово будет сравниваться со следующим словом из файла 1.txt
3.9 если файл 1.txt прочитан до конца, то закрываются оба файла 1.txt и 2.txt
3.10 файл 1.txt уничтожается
3.11 а файл 2.txt переименовывается - получает имя 1.txt

4. Программа прилагается.
...
Итак вопрос. Можно ли ускорить работу этой программы?
Возможны варианты
1. можно сравнивать по два слова из файла 1.txt и сразу, после сравнения, записывать их в файл 2.txt
2. можно разделить исходный файл 1.txt на два и более файлов. Отсортировать их по очереди и соединить в один. Как? А бог его знает ...
Слияние двух или более отсортированных файлов та еще задача. - Это целая тема или даже две темы.
3. можно все-таки использовать массив и тоже сортировать кусками. Массив, наверное, быстрее. Но я даже не знаю с какой стороны подойти к массиву.

QBasic/QuickBASIC
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
DIM t1 AS STRING
DIM t2 AS STRING
DIM tt AS STRING
 
CLS
OPEN "1.txt" FOR INPUT AS #1
 
DO
   LINE INPUT #1, t1
   N = N + 1
LOOP UNTIL EOF(1)
CLOSE #1
    
FOR i = 1 TO N
   OPEN "1.txt" FOR INPUT AS #1
   OPEN "2.txt" FOR APPEND AS #2
        
   LINE INPUT #1, t1
 
   DO
      LINE INPUT #1, t2
      IF t1 > t2 THEN
         tt = t1: t1 = t2: t2 = tt
      END IF
      PRINT #2, t1
      t1 = t2
      IF EOF(1) THEN PRINT #2, t1
   LOOP UNTIL EOF(1)
        
   CLOSE #1, #2
   KILL "1.txt"
   NAME "2.txt" AS "1.txt"
NEXT i

@m-ch · 30.08.2018, 08:39

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

величина файла такова, что его не удастся поместить в массив и потом этот массив
сортировать обычным способом.

Для современных языков указанный размер легко помещается в массив и сортируется

если же хотите сортировать непосредственно из фала, то попробуйте реализовать сортировку слиянием, возможно она подойдет для текущей задачи

Добавлено через 1 минуту

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

Слияние двух или более отсортированных файлов та еще задача

На мой взгляд достаточно тривиальная задача, реализуется достаточно просто

@wer1 · 30.08.2018, 08:55 **[ТС]**

Уважаемый мастер программирования m-ch,
спасибо вам за предоставленную мне информацию о сортировке.
Я собираюсь воспользоваться сортировкой слиянием. Файл будет разбит на 10
примерно равных частей и каждая часть отсортирована отдельно. Потом будет
попарное слияние ... ?
Тут я подумал... А нельзя ли слить все файлы в один СРАЗУ? ... это подумать надо...
Ещё раз большое вам спасибо!!!

@m-ch · 30.08.2018, 14:50

Реализовал сортировку на FreeBasic
Кода получилось достаточно много:

PureBasic
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
Declare Sub MyQsortTxt(sArr() As String, iArr() As Integer, start As Integer, finish As Integer)
 
Const BSize = 10000
Dim ff As Integer, ff1 As Integer, ff2 As Integer
Dim txt As String, txt1 As String, txt2 As String, b1 As Integer, b2 As Integer
Dim i As Integer, j As Integer, k As Integer
Dim sArr(1 To BSize) As String, iArr(1 To BSize) As Integer
Dim tmr As Double
 
tmr = Timer
Kill "output.txt"
ff = FreeFile
Open "input.txt" for input As #ff
While Not Eof(ff)
    Line Input #ff, txt
    i = i + 1
    sArr(i) = txt
    iArr(i) = i
    If i Mod BSize = 0 Or Eof(ff) Then
        MyQsortTxt sArr(), iArr(), 1, i
        j = j + 1       
        ff1 = FreeFile
        Open LTrim$(Str$(j)) + ".txt" for Output As #ff1
        For k = 1 To i
            Print #ff1, sArr(iArr(k))
        Next k
        Close #ff1
        i = 0
    End If      
Wend
Close #ff
 
Do While j > 1
    k = 0
    For i = 1 To j Step 2
        k = k + 1
        If i = j Then
            Print "Block"; i; " from"; j
            Name LTrim$(Str$(i)) + ".txt" As LTrim$(Str$(k)) + ".txt"
        Else
            Print "Block"; i; " And"; i + 1; " from"; j
            ff1 = FreeFile
            Open LTrim$(Str$(i)) + ".txt" For Input As #ff1
            ff2 = FreeFile
            Open LTrim$(Str$(i + 1)) + ".txt" For Input As #ff2
            ff = FreeFile
            Open "0.txt" For Output As #ff
            b1 = 0
            b2 = 0
            While Not Eof(ff1) And Not Eof(ff2)
                If b1 = 0 Then Line Input #ff1, txt1: b1 = -1
                If b2 = 0 Then Line Input #ff2, txt2: b2 = -1
                If txt1 < txt2 Then
                    b1 = 0
                    Print #ff, txt1
                Else
                    b2 = 0
                    Print #ff,txt2
                End If
            Wend
            If b1 Then Print #ff, txt1
            If b2 Then Print #ff, txt2
            While Not Eof(ff1)
                Line Input #ff1, txt1
                Print #ff, txt1
            Wend
            While Not Eof(ff2)
                Line Input #ff2, txt2
                Print #ff, txt2
            Wend    
            Close
            Kill LTrim$(Str$(i)) + ".txt" 
            Kill LTrim$(Str$(i + 1)) + ".txt"
            Name "0.txt" As LTrim$(Str$(k)) + ".txt"
        End If
    Next i
    j = k
Loop
Name "1.txt" As "output.txt"
Print "Time:"; Timer - tmr
Sleep 1000
 
Sub MyQsortTxt(sArr() As String, iArr() As Integer, start As Integer, finish As Integer)
    Dim i As Integer, j As Integer, x As String
    i = start
    j = finish
    x = sArr(iArr((i + j) \ 2))
    While i <= j
        While sArr(iArr(i)) < x: i = i + 1: Wend
        While sArr(iArr(j)) > x: j = j - 1: Wend
        If i <= j Then 
            Swap iArr(i), iArr(j)
            i = i + 1
            j = j - 1
        End If
    Wend
    If j > start Then MyQsortTxt sArr(), iArr(), start, j
    If i < finish Then MyQsortTxt sArr(), iArr(), i, finish
End Sub

Принцип работы:
Скачиваем файл блоками размерами BSize строк
Блоки сортируем быстрой сортировкой и сохраняем каждый блок в отдельном файле
Отсортированные файлы объединяем слиянием

Файл почти в 2 млн строк и размером 20 Мб сортируется в FreeBasic у меня за 25 секунд
Возможно не будет работать в QBasic

@m-ch · 30.08.2018, 16:43

не совсем корректно сортирует, есть небольшая ошибка при слиянии файлов

@m-ch · 30.08.2018, 17:08

Внес корректировку в код

PureBasic
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
Declare Sub MyQsortTxt(sArr() As String, iArr() As Integer, start As Integer, finish As Integer)
 
Const BSize = 10000
Dim ff As Integer, ff1 As Integer, ff2 As Integer
Dim txt As String, txt1 As String, txt2 As String, b1 As Integer, b2 As Integer
Dim i As Integer, j As Integer, k As Integer
Dim sArr(1 To BSize) As String, iArr(1 To BSize) As Integer
Dim tmr As Double
 
tmr = Timer
Kill "output.txt"
ff = FreeFile
Open "input.txt" for input As #ff
While Not Eof(ff)
    Line Input #ff, txt
    i = i + 1
    sArr(i) = txt
    iArr(i) = i
    If i Mod BSize = 0 Or Eof(ff) Then
        MyQsortTxt sArr(), iArr(), 1, i
        j = j + 1
        Print "Block:"; j, "Size:"; i       
        ff1 = FreeFile
        Open LTrim$(Str$(j)) + ".txt" for Output As #ff1
        For k = 1 To i
            Print #ff1, sArr(iArr(k))
        Next k
        Close #ff1
        i = 0
    End If      
Wend
Close #ff
 
Do While j > 1
    k = 0
    For i = 1 To j Step 2
        k = k + 1
        If i = j Then
            Print "Block"; i; " from"; j
            Name LTrim$(Str$(i)) + ".txt" As LTrim$(Str$(k)) + ".txt"
        Else
            Print "Block"; i; " And"; i + 1; " from"; j
            ff1 = FreeFile
            Open LTrim$(Str$(i)) + ".txt" For Input As #ff1
            ff2 = FreeFile
            Open LTrim$(Str$(i + 1)) + ".txt" For Input As #ff2
            ff = FreeFile
            Open "0.txt" For Output As #ff
            b1 = 0
            b2 = 0
            While Not Eof(ff1) Or Not Eof(ff2)
                If b1 = 0 And Not Eof(ff1) Then Line Input #ff1, txt1: b1 = -1
                If b2 = 0 And Not Eof(ff2) Then Line Input #ff2, txt2: b2 = -1
                If txt1 < txt2 And b1 <> 0 Or b2 = 0 Then
                    b1 = 0
                    Print #ff, txt1
                Else
                    b2 = 0
                    Print #ff,txt2
                End If
            Wend
            If b1 Then Print #ff, txt1 
            If b2 Then Print #ff, txt2
            Close
            Kill LTrim$(Str$(i)) + ".txt" 
            Kill LTrim$(Str$(i + 1)) + ".txt"
            Name "0.txt" As LTrim$(Str$(k)) + ".txt"
        End If
    Next i
    j = k
Loop
Name "1.txt" As "output.txt"
Print "Time:"; Timer - tmr
Sleep 1000
 
Sub MyQsortTxt(sArr() As String, iArr() As Integer, start As Integer, finish As Integer)
    Dim i As Integer, j As Integer, x As String
    i = start
    j = finish
    x = sArr(iArr((i + j) \ 2))
    While i <= j
        While sArr(iArr(i)) < x: i = i + 1: Wend
        While sArr(iArr(j)) > x: j = j - 1: Wend
        If i <= j Then 
            Swap iArr(i), iArr(j)
            i = i + 1
            j = j - 1
        End If
    Wend
    If j > start Then MyQsortTxt sArr(), iArr(), start, j
    If i < finish Then MyQsortTxt sArr(), iArr(), i, finish
End Sub

@wer1 · 30.08.2018, 18:18 **[ТС]**

Уважаемый мастер m-ch,
я благодарен вам за предоставленный вами удивительный код. Я бы до
такого точно бы не додумался. Но вот появилась ещё мысль ...
А что если исходный текстовый файл преобразовать в файл прямого доступа.
Ведь это будет нечто подобное массиву только в файловом виде. Мне очень
интересно ваше мнение. Скорость сортировки повысится? Или нет? Ведь файлы
всё-же не массивы ...

@m-ch · 31.08.2018, 08:21

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

Немного ускорил программу сортировки (во вложении) за счет сокращения лишних сравнений строк.
Файл состоящий из 500 тыс. строк (размером 5 МБ сортируется за 3 секунды
Протестировал на большом файле - 100 млн строк размером в 1 ГБ, все нормально сортирует, но затрачивает много времени.

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	30.08.2018, 08:55 [ТС]
	Уважаемый мастер программирования m-ch, спасибо вам за предоставленную мне информацию о сортировке. Я собираюсь воспользоваться сортировкой слиянием. Файл будет разбит на 10 примерно равных частей и каждая часть отсортирована отдельно. Потом будет попарное слияние ... ? Тут я подумал... А нельзя ли слить все файлы в один СРАЗУ? ... это подумать надо... Ещё раз большое вам спасибо!!! 0

@m-ch 6180 / 945 / 313 Регистрация: 25.02.2011 Сообщений: 1,381 Записей в блоге: 1
	30.08.2018, 16:43
	не совсем корректно сортирует, есть небольшая ошибка при слиянии файлов 0

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	30.08.2018, 18:18 [ТС]
	Уважаемый мастер m-ch, я благодарен вам за предоставленный вами удивительный код. Я бы до такого точно бы не додумался. Но вот появилась ещё мысль ... А что если исходный текстовый файл преобразовать в файл прямого доступа. Ведь это будет нечто подобное массиву только в файловом виде. Мне очень интересно ваше мнение. Скорость сортировки повысится? Или нет? Ведь файлы всё-же не массивы ... 0