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

@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 ГБ, все нормально сортирует, но затрачивает много времени.

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: показать затраченные материалы за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@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

Опции темы