Что нового

Аналог ассоциативного массива

Oki

Продвинутый
Сообщения
452
Репутация
63
А что по поводу скорости работы с такими массивами?
Оставляет желать лучшего.

Или я что-то не так делаю? Для теста скармливаю файл с текстовыми ключами, в котором порядка сотни миллионов строк длины порядка двух десятков символов, но лишь порядка шести сотен строк-ключей уникальны. Вот мой скрипт на AutoIt.
Код:
$sFileIn = @ScriptDir & "\keys.txt"
$hFileIn = FileOpen($sFileIn)
$oDict = ObjCreate("Scripting.Dictionary")
Do
   $sText = FileReadLine($hFileIn)
   $flagEOF = @error
   If $flagEOF <> -1 Then
      If $oDict.Exists($sText) Then
         $oDict.Item($sText) += 1
      Else
         $oDict.Add($sText, 1)
      EndIf
   EndIf
Until $flagEOF = -1
$aKeys = $oDict.Keys()
For $i In $aKeys
   ConsoleWrite($i & @TAB & $oDict.Item($i) & @CRLF)
Next
FileClose($hFileIn)
А вот мой код на C++.
Код:
#include <iostream>
#include <fstream>
#include <unordered_map>
using namespace std;
int main() {
    ifstream in("keys.txt");
    string str;
    int count;
    unordered_map<string, int> info;
    unordered_map<string, int>::iterator iter;
    while (!in.eof()) {
        getline(in, str);
        if ((str != "") || !in.eof()) {
            iter = info.find(str);
            if (iter == info.end()) {
                info[str] = 1;
            }
            else {
                info[str] += 1;
            }
        }
    }
    in.close();
    for (auto x : info) {
        cout << x.first << "\t" << x.second << "\n";
    }
}
Оба считают для каждого ключа количество повторений в файле. Вполне ожидаемо, что скорость второго кода более высока: C++ всегда шустрее, чем AutoIt. Но вот соотношение скоростей ошеломляет. Тест показал, что первый скрипт отработал аж в 40 раз медленнее. Горю желанием услышать, что всё дело лишь в том, что мой скрипт неэффективно написан, так как иначе такие большие данные придётся обрабатывать иными средствами.
 

Norm

Продвинутый
Сообщения
291
Репутация
76
Конечно не весть какое ускорение, но всё же в более чем 2х быстрее (тоесть было в 40 стало меньше чем в 20)
Но и это больше оптимизация, чем решение
Код:
$sFileIn = @ScriptDir & "\keys.txt"
$hFileIn = FileOpen($sFileIn)
$aText = FileReadToArray($hFileIn)
FileClose($hFileIn)
$oDict = ObjCreate("Scripting.Dictionary")
For $nN = 0 To UBound($aText)-1
    $oDict.Item($aText[$nN]) = 1
 Next
$aKeys = $oDict.Keys()
ConsoleWrite(UBound($aKeys) & @CRLF)
 
Последнее редактирование:

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Горю желанием услышать, что всё дело лишь в том, что мой скрипт неэффективно написан
Для скорости рекомендуется:
1. Считывать сразу весь файл, FileReadLine в цикле очень замедляет обработку
2. Использовать как можно меньше условий в цикле, каждое условие влияет на уменьшение скорости
Тут есть несколько примеров

Вот мои варианты решения вашей задачи

Код:
#include <Array.au3>

$sFile='D:\Test.txt'
$aRes=__File_Get_Count_Lines($sFile)
_ArrayDisplay($aRes)

; $aRes=__File_Get_Count_Lines_Map($sFile)
; _ArrayDisplay($aRes)

; Получение уникальных строк и их количества, реализация через Scripting.Dictionary
Func __File_Get_Count_Lines($sFile,$iRegistr=0,$iMode=3)
  Local $oDict=ObjCreate('Scripting.Dictionary'),$aRet=FileReadToArray($sFile)
  $oDict.CompareMode=$iRegistr
  For $i In $aRet
    $oDict.Item($i)+=1
  Next
  Switch $iMode
    Case 0
      Return $oDict.Keys
    Case 1
      Return $oDict.Items
    Case 2
      Local $aKey=$oDict.Keys,$aItems=$oDict.Items,$iCount=UBound($aKey),$aRet[$iCount][2]
      For $i=0 To $iCount-1
        $aRet[$i][0]=$aKey[$i]
        $aRet[$i][1]=$aItems[$i]
      Next
      Return $aRet
    Case 3 ; оптимальнее, чем $iMode=2, т.к. не дублируются массивы в переменные $aKey и $aItems
      ; $iCount=$oDict.Count
      Local $aRet[$oDict.Count][2],$n=0
      For $i In $oDict.Keys
        $aRet[$n][0]=$i
        $aRet[$n][1]=$oDict.Item($i)
        $n+=1
      Next
      Return $aRet
  EndSwitch
EndFunc

; Получение уникальных строк и их количества, реализация через Map функции
Func __File_Get_Count_Lines_Map($sFile,$iMode=2)
  Local $aRet=FileReadToArray($sFile),$mMap[]
  For $i In $aRet
    $mMap[$i]+=1
  Next
  Switch $iMode
    Case 0
      Return MapKeys($mMap)
    Case 1
      Local $aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount],$n=0
      For $i In $aKey
        $aRet[$n]=$mMap[$i]
        $n+=1
      Next
      Return $aRet
    Case 2
      Local $aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount][2],$n=0
      For $i In $aKey
        $aRet[$n][0]=$i
        $aRet[$n][1]=$mMap[$i]
        $n+=1
      Next
      Return $aRet
  EndSwitch
EndFunc
 

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Если вы желаете пользоваться этим функционалом, то необходимо обновиться, в какой версии эти функции появились, сказать не могу, но уже несколько лет точно.
Последняя версия 3.3.16.0 (6th March, 2022)
 

Norm

Продвинутый
Сообщения
291
Репутация
76
У меня предпоследняя версия, которую использую последние два года.
Обновиться пока не решился. Наверное придётся всё же сделать это.
 

Oki

Продвинутый
Сообщения
452
Репутация
63
Код:
$aText = FileReadToArray($hFileIn)
Для скорости рекомендуется:
1. Считывать сразу весь файл
Куда считывать? В массив весь файл невозможно считать из-за ограничений на размеры массивов. Да и вряд ли построчное чтение файла является существенным замедлением на фоне неторопливой работы с ассоциативными массивами в AutoIt в принципе.
 

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Да и вряд ли построчное чтение файла является существенным замедлением

Конечно вы не правы, пройдитесь по форуму поиском - есть 10-ки тестов в разных темах.
Мне просто интересно:
1. Это что за файл такой в "порядка сотни миллионов строк" и сколько он весит...
Я создал файл в 6 млн. строк он весит примерно 60 Mb
Функция, которую я дал __File_Get_Count_Lines отработала ~40 сек.
2. Что за программа создаёт такой файл с одинаковыми строками...
Может изначально их ловить при создании
3. И последнее: чем вы открываете такой файл, как я понимаю он весит несколько гигов...

неторопливой работы с ассоциативными массивами в AutoIt в принципе
Ну и это далеко совсем не так... Сам встречал кучу кода/функций на vbs, js, Cи ... которые работали далеко не быстро... Сотни функций переписал под себя тестируя скорость...
 

Oki

Продвинутый
Сообщения
452
Репутация
63
Конечно вы не правы, пройдитесь по форуму поиском - есть 10-ки тестов в разных темах.
Я же не утверждаю, что построчное чтение файлов совсем не замедляет. Речь лишь о том, что на фоне времени заполнения ассоциативного массива это относительно мелочь.
Я создал файл в 6 млн. строк он весит примерно 60 Mb
Функция, которую я дал __File_Get_Count_Lines отработала ~40 сек.
Над файлом около двух гигабайт, в котором чуть более 600 уникальных ключей, чьи длины в среднем чуть более 20 символов, скрипт на AutoIt трудился 35 минут, а программа на C++ справилась за 52 секунды. Пожалуй, её и буду вызывать из основного скрипта, в котором останется собственно автоматизация без вычислительной работы.
 

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Oki, спасибо за ответ, в любом случае всё не зря...
Стало интересно - Никогда не тестировал те функции, которые публиковал на скорость и был в шоке...
С помощью MAP, который встроен в Autoit, получается в 2-4 раза быстрее получить результат при этой конкретной задаче.

Результаты в секундах...

Выдаёт функция __File_Get_Count_Lines()
$iDiff_1 =>5.2486554<=
$iDiff_2 =>27.0500738<=
$iDiff_3 =>2.677511<=
Всего =>34.9762402<=

Выдаёт функция __File_Get_Count_Lines_Map()
$iDiff_1 =>4.8781233<=
$iDiff_2 =>5.5376301<=
$iDiff_3 =>2.6255719<=
Всего =>13.0413253<=
------
$iDiff_1 - чтение файла в массив - примерно 6 млн. строк, 60 мб
$iDiff_2 - заполнение базы ассоциативного массива
$iDiff_3 - создание 2D массива

Кому интересно ещё раз публикую со счётчиками...

Код:
#include <Array.au3>

$sFile='D:\Большой_текст.txt'


$aRes=__File_Get_Count_Lines($sFile)
_ArrayDisplay($aRes)

; $aRes=__File_Get_Count_Lines_Map($sFile)
; _ArrayDisplay($aRes)

; Получение уникальных строк и их количества, реализация через Scripting.Dictionary
Func __File_Get_Count_Lines($sFile,$iRegistr=0,$iMode=3)
  Local $hTimer=TimerInit(),$iDiff_1,$iDiff_2,$iDiff_3
  Local $oDict=ObjCreate('Scripting.Dictionary'),$aRet=FileReadToArray($sFile)
 
  $iDiff_1=TimerDiff($hTimer)/1000
  $hTimer=TimerInit()
 
  $oDict.CompareMode=$iRegistr
  For $i In $aRet
    $oDict.Item($i)+=1
  Next
 
  $iDiff_2=TimerDiff($hTimer)/1000
  $hTimer=TimerInit()
 
  Switch $iMode
    Case 0
      Return $oDict.Keys
    Case 1
      Return $oDict.Items
    Case 2
      Local $aKey=$oDict.Keys,$aItems=$oDict.Items,$iCount=UBound($aKey),$aRet[$iCount][2]
      For $i=0 To $iCount-1
        $aRet[$i][0]=$aKey[$i]
        $aRet[$i][1]=$aItems[$i]
      Next
      Return $aRet
    Case 3 ; оптимальнее, чем $iMode=2, т.к. не дублируются массивы в переменные $aKey и $aItems
      ; $iCount=$oDict.Count
      Local $aRet[$oDict.Count][2],$n=0
      For $i In $oDict.Keys
        $aRet[$n][0]=$i
        $aRet[$n][1]=$oDict.Item($i)
        $n+=1
      Next
      $iDiff_3=TimerDiff($hTimer)/1000
      MsgBox(4096,'Результат ','$iDiff_1 =>'&$iDiff_1&'<='&@CRLF&'$iDiff_2 =>'&$iDiff_2&'<='&@CRLF&'$iDiff_3 =>'&$iDiff_3&'<='&@CRLF&'Всего =>'&$iDiff_1+$iDiff_2+$iDiff_3&'<=')

      Return $aRet
  EndSwitch
EndFunc

; Получение уникальных строк и их количества, реализация через Map функции
Func __File_Get_Count_Lines_Map($sFile,$iMode=2)
  Local $hTimer=TimerInit(),$iDiff_1,$iDiff_2,$iDiff_3
  Local $aRet=FileReadToArray($sFile),$mMap[]
 
  $iDiff_1=TimerDiff($hTimer)/1000
  $hTimer=TimerInit()

 
  For $i In $aRet
    $mMap[$i]+=1
  Next
 
  $iDiff_2=TimerDiff($hTimer)/1000
  $hTimer=TimerInit()

 
  Switch $iMode
    Case 0
      Return MapKeys($mMap)
    Case 1
      Local $aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount],$n=0
      For $i In $aKey
        $aRet[$n]=$mMap[$i]
        $n+=1
      Next
      Return $aRet
    Case 2
      Local $aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount][2],$n=0
      For $i In $aKey
        $aRet[$n][0]=$i
        $aRet[$n][1]=$mMap[$i]
        $n+=1
      Next
      $iDiff_3=TimerDiff($hTimer)/1000
      MsgBox(4096,'Результат ','$iDiff_1 =>'&$iDiff_1&'<='&@CRLF&'$iDiff_2 =>'&$iDiff_2&'<='&@CRLF&'$iDiff_3 =>'&$iDiff_3&'<='&@CRLF&'Всего =>'&$iDiff_1+$iDiff_2+$iDiff_3&'<=')

      Return $aRet
  EndSwitch
EndFunc

Сообщение автоматически объединено:

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

Код:
#include <Array.au3>

$sFile='D:\Большой_текст.txt'

Local $hTimer=TimerInit(),$iDiff_1

$aRes=__ReadLine_Get_Count_Lines_Map($sFile)

$iDiff_1=Int(TimerDiff($hTimer)/1000)
MsgBox(4096,'Итого','Итого: '&$iDiff_1&' секунд')

_ArrayDisplay($aRes)


Func __ReadLine_Get_Count_Lines_Map($sFile)
  Local $mMap[],$hFile=FileOpen($sFile),$sLine=FileReadLine($hFile)
  While @error+1
    $mMap[$sLine]+=1
    $sLine=FileReadLine($hFile)
  WEnd
  Local $0=FileClose($hFile),$aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount][2],$n=0
  For $i In $aKey
    $aRet[$n][0]=$i
    $aRet[$n][1]=$mMap[$i]
    $n+=1
  Next
  Return $aRet
EndFunc
 
Последнее редактирование:

AZJIO

Меценат
Меценат
Сообщения
2,892
Репутация
1,196
Интересно измерить скорость FileReadLine($hFile), так как даже в PureBasic поднимался вопрос что построчное сохранение работает намного медленнее, чем сохранение одним потоком, а для цикла AutoIt3 как раз зависимость от числа итераций (миллион) и неоптимизированность содержимого цикла, остальное выполняется внутренними функциями на компилируемом машинном языке. Объект "Scripting.Dictionary" встроенный в Windows объект, а значит все действия с ним безопасны и оптимизированы.
Если есть желанием можете сравнить Compare_strings на PureBasic, где поиск уникальных строк сделан с помощью встроенной карты (Map). Спрашивал есть ли какие ограничения на длину строки в Map, ни в справке ни в ответах не было сказано об ограничении. Логически алгоритм оптимизирован, добавление элемента проверяет есть ли уже существующий, то есть пробежаться по всем элементам внутри карты и скорость этого не является каким то особым алгоритмом, происходит сравнение двух ячеек памяти по указателю и первое несовпадение приводит к переходу следующего сравнения. И этот порядок проверки не ускорить, как я понимаю он что в "Scripting.Dictionary", что в Map (PureBasic) думаю написан идеально, ни добавить ни убавить.
 

Oki

Продвинутый
Сообщения
452
Репутация
63
Логически алгоритм оптимизирован, добавление элемента проверяет есть ли уже существующий, то есть пробежаться по всем элементам внутри карты и скорость этого не является каким то особым алгоритмом, происходит сравнение двух ячеек памяти по указателю и первое несовпадение приводит к переходу следующего сравнения. И этот порядок проверки не ускорить, как я понимаю он что в "Scripting.Dictionary", что в Map (PureBasic) думаю написан идеально, ни добавить ни убавить.
Да ладно! А как же многочисленные реализации, имеющие сложность O(1)? Причём независящую не только от количества уникальных ключей, но от их длин.
 

Prog

Продвинутый
Сообщения
598
Репутация
77
Для теста скармливаю файл с текстовыми ключами, в котором порядка сотни миллионов строк длины порядка двух десятков символов, но лишь порядка шести сотен строк-ключей уникальны.
Если файл не содержит конфиденциальных данных, упакуйте его в 7z и выложите здесь.
Будет проще найти места требующие оптимизации.

Вот мой скрипт на AutoIt.
Сколько времени выполняется этот участок по сравнению с полным кодом?
Код:
$sFileIn = @ScriptDir & "\keys.txt"
$hFileIn = FileOpen($sFileIn)
;$oDict = ObjCreate("Scripting.Dictionary")
Do
   $sText = FileReadLine($hFileIn)
   $flagEOF = @error
   If $flagEOF <> -1 Then
;       If $oDict.Exists($sText) Then
;          $oDict.Item($sText) += 1
;       Else
;          $oDict.Add($sText, 1)
;       EndIf
   EndIf
Until $flagEOF = -1


Пожалуй, её и буду вызывать из основного скрипта, в котором останется собственно автоматизация без вычислительной работы.
Участки кода требующие высокой скорости выполнения, логичнее написать на более быстрых ЯП и скомпилировать в dll.

Спрашивал есть ли какие ограничения на длину строки в Map, ни в справке ни в ответах не было сказано об ограничении.
Могу предположить что ограничений на строки нет. Есть на объем памяти процесса и доступной памяти.
 

AZJIO

Меценат
Меценат
Сообщения
2,892
Репутация
1,196
Да ладно! А как же многочисленные реализации, имеющие сложность O(1)? Причём независящую не только от количества уникальных ключей, но от их длин.
я же объяснил минимальный ход алгоритма для определения. Невозможно волшебным способом не проверяя выдать заключение что это дубликат. Если только из серии "земля плоская".
 

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Интересно, что в последней версии Autoit (в истории) нет записи когда появились функции MAP...
Если в "Scripting.Dictionary" есть Count , то в Map я не нашёл как проще найти количество - через ряд тестирований нашёл - UBound($mMap), тогда можно ещё сократить код.... , хотя , как я понял это уже никому не нужно)))
Код:
Func __ReadLine_Get_Count_Lines_Map($sFile)
  Local $mMap[],$hFile=FileOpen($sFile),$sLine=FileReadLine($hFile)
  While @error+1
    $mMap[$sLine]+=1
    $sLine=FileReadLine($hFile)
  WEnd
;   Local $0=FileClose($hFile),$aKey=MapKeys($mMap),$iCount=UBound($aKey),$aRet[$iCount][2],$n=0
  Local $0=FileClose($hFile),$aRet[UBound($mMap)][2],$n=0
  For $i In MapKeys($mMap)
    $aRet[$n][0]=$i
    $aRet[$n][1]=$mMap[$i]
    $n+=1
  Next
  Return $aRet
EndFunc
 

Oki

Продвинутый
Сообщения
452
Репутация
63
Сколько времени выполняется этот участок по сравнению с полным кодом?
Больше, чем мне казалось, но всё-таки меньшую часть общего времени. Последние тесты и размышления подталкивают в целом поменять стратегию и комбинировать вычислительные способности одних языков программирования с простотой автоматизации в скриптах. То, что AutoIt растёт в плане различных средств, хорошо для случаев, требующих небольших ресурсов.
 

Andrey_A

Продвинутый
Сообщения
325
Репутация
68
Сколько времени выполняется этот участок по сравнению с полным кодом?
Посмотрите мой код - участок - там меньше проверок и на большом объёме быстрее - хотя по-моему не принципиально

Oki, а мой код. как я понял, на своём большом файле вы так и не тестировали... а то бы опубликовали время тестирования..., ну да ладно
 
Последнее редактирование:

Oki

Продвинутый
Сообщения
452
Репутация
63
Участки кода требующие высокой скорости выполнения, логичнее написать на более быстрых ЯП и скомпилировать в dll.
А наоборот можно делать? То есть создавать dll из AutoIt-скрипта, а использовать в других языках? Или по причине подхода, при котором фактически компиляция всё равно приводит к упакованному интерпретатору, это невозможно?
Сообщение автоматически объединено:

я же объяснил минимальный ход алгоритма для определения. Невозможно волшебным способом не проверяя выдать заключение что это дубликат. Если только из серии "земля плоская".
Это заблуждение, есть довольно стандартные (но не слишком простые) современные алгоритмические хитрости, которые позволяют не устраивать столь затратные проверки.
Сообщение автоматически объединено:

а мой код. как я понял, на своём большом файле вы так и не тестировали...
Да он у меня с первой попытки вообще не запустился, а разбираться пока было некогда. Я в целом в процессе принятия решения отказываться делать подобную работу на AutoIt. Надо начинать отделять мух от котлет.
 
Последнее редактирование:

AZJIO

Меценат
Меценат
Сообщения
2,892
Репутация
1,196
современные алгоритмические хитрости
есть минимальное человеческое телодвижение для различия дубликатов и всякие хитрости это всего лишь техническое приближение к человеческому логическому мышлению. Просто алгоритмы в виртуальной логике не равно техническому исполнению. Если я хочу проверить отсутствие дубликата, то должен проверить различие с каждым иного не дано, я должен сделать этот минимум. Проверять до конца не обязательно достаточно первое несовпадение в строке. Какую тут хитрость можно придумать? Факты в студию иначе зачем говорить, разводить демагогию, типа у меня своё мнение, я так считаю.

К пример в теме мне предложили алгоритм Блума, я конечно не понял сути, ведь он использует тот же алгоритм, если только карта использует не тот алгоритм который подразумеваю я, но объяснения нет и я использую то что понимаю, а то что в википедии сказано о ложноположительном и ложноотрицательном срабатывании меня уже отталкивает своей неопределённостью. Если в алгоритме есть дыра которая позволяет тебе с 99% точностью найти быстро дубликаты, а второй со долго но со 100%, то конечно я выбираю последний.

И ещё вариант, к примеру можно построить древовидную структуру данных, например первый символ 1 из 16 и в первом родительском дереве максимум 16 деревьев, далее в каждом из этих 16 ещё максимум 16 и т.д. Но чтобы работать с такой структурой надо её создать, что если время на её создание равно времени на однократное проверку дубликатов, получается если ты сравниваешь с некоторым подготовленным массивом данных это одно, но в реальности мы сравниваем случайные данные и не повторяем это, а значит построение такой структуры не даёт ускорения.
 

Oki

Продвинутый
Сообщения
452
Репутация
63
зачем говорить, разводить демагогию, типа у меня своё мнение, я так считаю.
А, так все эти выкладки, оказывается, демагогия? Нет, я всё же склонен считать, что это искреннее заблуждение. Не оговаривай себя.
Сообщение автоматически объединено:

Если в алгоритме есть дыра которая позволяет тебе с 99% точностью найти быстро дубликаты, а второй со долго но со 100%, то конечно я выбираю последний.
Нет-нет, речь о безошибочных детерминистических алгоритмах. Я не утверждаю, что могу такой алгоритм создать самостоятельно, мне не попадалось описание с достаточным количеством деталей, но у меня достаточно примерного понимания темы, чтобы не спорить с достаточно известной истиной.
 
Верх