Форум » [x]Harbour » Ascan ? » Ответить
Ascan ?
Dima: [pre2] Есть массив вида {{},{},{}} поиск веду в первом элементе do while !eof() .. if ascan(klnmas[1],{|fff| fff==nakl_r1->kod_kl})==0 skip loop endif ....... skip enddo медленновато что то или меня уже плющит.... есть какой то другой аналог Ascan который пошустрее работает ? Понятно что вот так быстрее будет if ascan(klnmas[1],nakl_r1->kod_k)==0 skip loop endif RDD скипает быстрее чем работает Ascan с блоком кода.... [/pre2]
Ответов - 44, стр:
1 2 3 All
Pasha: Поиск в ascan выполняется методом полного перебора массива, так что это медленный поиск. С использованием блока кода он будет еще медленнее, но и без блока кода медленно. Особенно в большом массиве. Особенно в цикле. Насчет того, чем заменить: у меня этих ascan'ов хоть пруд пруди. Вкратце их алгоритм: надо при заполнении массива сразу его сортировать, и использовать быстрый поиск в отсортированном массиве. Но точно так же работает хэш, так что может быть стоит использовать вместо моих нестандартных функций стандартные средства харбора для работы с хэш. Если я правильно понял твою задачу, ты формируешь двумерный массив с размерностями 3*n, где в первом подмассиве хранятся ключи, а в двух следующих - соответствующие им данные. Если "перевернуть" массив, т.е. использовать размерности не 3*n, а n*3, то можно будет использовать хэш, примерно как в примере Петра: http://clipper.borda.ru/?1-4-0-00000784-000-0-0-1354477086 только можно вместо _AADD(hDim,{495, 1}) вызывать _AADD(hDim,{495, x1, x2, ...}) т.е. варьировать 2-ю размерность Ну а свою функцию я когда-то давно выкладывал в теме: https://groups.google.com/forum/#!topicsearchin/comp.lang.xharbour/sorted$20array/comp.lang.xharbour/b0jKrNhcNAk в этой же теме Пшемек рассказывает, как использовать хеш
petr707: В этой задаче можно завершать поиск , если хотя бы один элемент найден, как делает ASCAN2() (см. ниже) в отличие от ASCAN(), который все равно проверяет весь массив. Function ascan2(arr,bl, nstart, nqu ) Local n:=0,m,L:=len(arr),nret:=0,nend Local lbl:= ( valtype(bl)="B") if nstart=NIL nstart=1 endif if nqu=NIL nend:=L else nend:=nstart-1+nqu endif for n=nstart to nend if lbl if eval(bl,arr[n]) nret :=n EXIT endif else if bl==arr[n] nret :=n EXIT endif endif//lbl next i return nret
Pasha: petr707 пишет: как делает ASCAN2() (см. ниже) в отличие от ASCAN(), который все равно проверяет весь массив. Неправда. ASCAN работает точно также. Когда искомый элемент найден, цикл сразу же завершается, и возвращается индекс элемента. В этом нетрудно убедиться, посмотрев на сырцы hb_arrayScan вот фрагмент этой функции для поиска строки в массиве: [pre2] else if( HB_IS_STRING( pValue ) ) { do { PHB_ITEM pItem = pBaseArray->pItems + nStart++; /* NOTE: The order of the pItem and pValue parameters passed to hb_itemStrCmp() is significant, please don't change it. [vszakats] */ if( HB_IS_STRING( pItem ) && hb_itemStrCmp( pItem, pValue, fExact ) == 0 ) return nStart; } while( --nCount > 0 ); } [/pre2] Поиск в этой функции реализован самым оптимальным образом. Но это не делает оптимальным сам алгоритм полного перебора.
Dima: Pasha Спасибо за подробный ответ ! Pasha пишет: Если я правильно понял твою задачу, ты формируешь двумерный массив с размерностями 3*n, где в первом подмассиве хранятся ключи, а в двух следующих - соответствующие им данные. Ну не совсем так. Изначально создается массив amas:={{},{},{}} c 3 элементами где каждый элемент массив. Затем я обрабатываю справочник контрагентов на предмет условий заданных юзером и заполняю первый элемент кодами контрагентов. Остальные 2 элемента так же заполняются соответствующими цифирками. После этого я обрабатываю журнал накладных , предварительно установив в нем SCOPE за интервал дат (по индексу типа DTOS(data_n)) и хожу в цикле проверяя массив (отсеивая не нужных контрагентов). Вот и все. Думаю сортировка массива скорости не прибавит так же как и работа с хэш. По любому этот отчет в Harbour cтроится в разы быстрее нежели в Clipper+SIX или Clipper+ADS. Просто хотелось еще не много ускорить ;)
Pasha: Dima пишет: Думаю сортировка массива скорости не прибавит так же как и работа с хэш. Для небольших массивов разница будет несущественной, а для больших - просто огромной. Вот к примеру такой тест: func main Local nSize := 10000, nI, nKey, nSec, nRes Local aDim := {}, aDim2 := {} Local hDim := { => } // заполнение массива и хеша for nI := 1 to nSize nKey := ((nI + Int(nSize/2)) % nSize) + 1 AADD(aDim, nKey) AADD(aDim2, nI) _AADD(hDim, nKey, nI) next nRes := 0 ? 'Array scan', len(aDim) nSec := Seconds() for nI := 1 to nSize nRes += aDim2[ASCAN(aDim, nI)] next ? (Seconds() - nSec)*1000, nRes nRes := 0 ? 'Hash scan', len(aDim) nSec := Seconds() for nI := 1 to nSize nRes += hDim[nI] next ? (Seconds() - nSec)*1000, nRes return nil PROCEDURE _AADD( aHash, nKey, nI ) aHash[nKey] := nI retu Размер nSize я взял 10000, чтобы время хоть как-то отличалось от нуля. Результат выводится в миллисекундах. Для массива у меня получилось 219 мс, для хеша - опять ноль. Если nSize задать 30000, то результат для массива будет 1953 мс, для хеша - 15мс. Разница в производительности выходит на порядки. Это все равно, что сравнивать разницу поиска с помощью skip и seek. Кстати, аналогия получается прямая, поскольку алгоритмы поиска при этом совершенно идентичны.
Dima: Pasha Буду мозговать , спасибо.
nick_mi: Я может не знаю всех дополнительных условий, но для приведенного выше алгоритма почему нельзя сделать индекс <Имя контрагента>+dtos (data) в журнале накладных . Для каждого кантрагента,попадающего под условия, отбираются данные за указанный интервал. В этом случае отпадает перебор по ascan () и отсекаются лишние движения по базе накладных.
Dima: Что то как то не привычны эти Hash и пока что потерялся ;) Как следующий код преобразовать к Hash массивам ? [pre2] ams:={{},{},{}} for i=1 to 100 aadd(ams[1], i ) aadd(ams[2],seconds()) aadd(ams[3],time()) next i:=ascan(ams[1],33) ? ams[1][ i ] ? ams[2][ i ] ? ams[3][ i ] [/pre2] Вот так что ли ..... [pre2] local ams:={=>} local npos for i=1 to 100 ams[ i ]:={seconds(),time()} next if HB_HHASKEY( ams, 33, @nPos ) ? hb_hget(ams,npos)[1] ? hb_hget(ams,npos)[2] endif [/pre2]
SergKis: Dima пишет:Что то как то не привычны эти Hash и пока что потерялся Может поможет: [pre2] oH := bkHash():New() oH:Put('001', aa->Field10) xVal := oH:Get('001', 'NotFound') oH:Sum(cTabNr, zpl->R_16) // DB zarpl. oH:Sum(cTabNr, -(zpl->R_DLT) // DB zarpl. CLASS bkHash VAR oHash _METHOD New() _METHOD Get( xKey, xVal ) _METHOD Put( xKey, xVal ) _METHOD Len() _METHOD Del( xKey ) _METHOD IsKey( xKey ) _METHOD GetI( nElem, lArr ) _METHOD Sum( xKey, xVal ) ENDCLASS METHOD New() CLASS bkHash ::oHash := hb_hash() RETURN Self METHOD Get( xKey, xDef ) CLASS bkHash // IF hb_hHasKey( ::oHash, xKey ); RETURN ::oHash[xKey] // ENDIF RETURN hb_hGetDef( oHash, xKey, xDef) METHOD Put( xKey, xVal ) CLASS bkHash // ::oHash[xKey] := xVal hb_hSet( ::oHash, xKey, xVal ) RETURN .T. METHOD Len() CLASS bkHash RETURN Len(::oHash) METHOD Del( xKey ) CLASS bkHash IF hb_hHasKey( ::oHash, xKey ); hb_hDel(::oHash, xKey) ENDIF RETURN NIL METHOD IsKey( xKey ) CLASS bkHash RETURN hb_hHasKey( ::oHash, xKey ) METHOD GetI( nElem, lArr ) CLASS bkHash IF empty(lArr); RETURN hb_hValueAt(::oHash, nElem) ENDIF RETURN { Hb_hKeyAt(::oHash, nElem), hb_hValueAt(::oHash, nElem) } METHOD Sum( xKey, xVal ) CLASS bkHash LOCAL aSum,i,k,t := valtype(xVal) IF t == "A" k := Len(xVal) aSum := Self:Get( xKey, aFill(array(k), 0) ) IF Len( aSum ) == k AEVal(xVal, {|x,i| aSum[ i ]:= iif(ValType(x)=='N', aSum[ i ]+x, x) } ) ELSE aSum := xVal ENDIF ELSEIF t == "N" aSum := ::Get( xKey, 0 ) IF valtype(aSum) == "N"; aSum += xVal ENDIF ELSE aSum := xVal ENDIF RETURN Self:Put(xKey, aSum) /* Интерфейс --------- hb_Hash( 1,2, ... , 5,6, ....) -> oHash // Много по два hb_hHasKey( oHash, xKey ) -> .T./.F. - наличие ключа hb_hPos( oHash, xKey) -> Позиция ключа hb_hGet( oHash, xKey) -> xValue или ошибка hb_hGetDef( oHash, xKey, xDef) -> если есть то xValue иначе xDef ошибка если oHash не то. hb_hSet( oHash, xKey, xVal) -> oHash добавляет или ставит hb_hDel( oHash, xKey) -> oHash Удаляет hb_hKeyAt( oHash, nPos) -> xKey С Ключ позиции hb_hValueAt( oHash, nPos, xVal) -> Значение с позиции hb_hPairAt( oHash, nPos, [DstKey, DstVal] ) -> { xKey, xVal } Если 3,4 параметры есть то замена иначе вернёт текущее hb_hDelAt( oHash, nPos) -> oHash hb_hKeys( oHash ) -> hb_hValues( oHash ) -> hb_hClear( oHash ) -> oHash hb_hFill( oHash, xVal) -> oHash hb_hClone( oHash ) -> oHash hb_hCopy( oHashSource, oHashDest) -> oHashDest hb_hMerge( oHashDest, oHashSource, bBlock | n ) -> oHashDest Если есть bBlock то на каждом елементе oHashDest выполняется {|xKey, xVal, nPos| ... } hb_hEVal( oHash, bBlock, [nStart], [nCount] ) -> oHash bBlock == {|xKey, xVal, nPos| ...} hb_hScan( oHash, xVal, [nStart],[nCount], [lExact] ) -> nPos | 0 hb_hSort( oHash ) -> oHash // Режимы hb_hCaseMath( oHash, lValue) -> .T. / .F. предыдущий Сравнение с учётом регистра hb_hBinary( oHash, lValue) -> .T. / .F. hb_hAutoAdd( oHash, lValue | nValue ) -> HB_HASH_AUTOADD_ALWAYS HB_HASH_AUTOADD_ASSIGN hb_hKeepOrder( oHash, lValue) -> .T. / .F. hb_hAllocate( oHash, nValue) -> NIL hb_hDefault( oHash, [xValue]) -> xValue получить поставить умалчивоемое Empty( oHash ) -> .T. если размер == 0 Len( oHash ) -> даёт размер Hash hb_IsHash( oHash ) -> .T./.F. hb_IsNul( oHash ) -> если длинна == 0 // ключ в Hash всегда уникальный Ошибки Всегда : oHash не то ( Base 1187 ) nPos не верное ( Base 1123 ) */ [/pre2]
Dima: SergKis Спасибо. Мне вот не понятна одна штука [pre2] aHash := {10=>, 20=>} ? HB_HHASKEY( aHash, 5, @nPos ), nPos // .F. 0 ? HB_HHASKEY( aHash, 10, @nPos ), nPos // .T. 1 ? HB_HHASKEY( aHash, 15, @nPos ), nPos // .F. 1 // почему не ноль ? ? HB_HHASKEY( aHash, 20, @nPos ), nPos // .T. 2 ? HB_HHASKEY( aHash, 25, @nPos ), nPos // .F. 2 // почему не ноль ? [/pre2]
Dima: В общем в первом приближении разобрался. Всем спасибо !
SergKis: SergKis пишет:Может поможет: Небольшой пример вдогонку:[pre2] ... LOCAL a,i,j LOCAL oTotal := bkHash():New() LOCAL oGroup := bkHash():New() LOCAL oTovar := bkHash():New() sele TOVAR INDEX DtoS(DateDok)+VidOper ... ... SetScope(0, DtoS(date())+'30') // документы реализации SetScope(0, DtoS(date())+'30') // за день dbGotop() DO WHILE ! eof() oTotal:Sum('Kol_Sum' , { 1, tovar->SUMMA }) oGroup:Sum(tovar->KodGru , { 1, tovar->KOLVO, tovar->SUMMA }) oTovar:Sum(tovar->KodTovar, { 1, tovar->KOLVO, tovar->SUMMA }) dbSkip(1) ENDDO ... ? ' Отчет о продажах за день :',date() ? '======================================================================' a := oTotal:Get( 'Kol_Sum' ) ? 'Всего: строк -', a[ 1 ], 'сумма -', a[ 2 ] ? '======================================================================' ? 'В том числе по группам:' for i := 1 to len( oGroup ) a := oGroup:GetI( i, .T. ) // return {KodGru,{...}} ? 'группа -', a[ 1 ], 'строк -', a[ 2 ][ 1 ], 'кол-во -', a[ 2 ][ 2 ], 'сумма -', a[ 2 ][ 3 ] next ? '======================================================================' ? 'В том числе по товару:' for i := 1 to len( oTovar ) a := oTovar:GetI( i, .T. ) // return {KodTovar,{...}} ? 'товар -', a[ 1 ], 'строк -', a[ 2 ][ 1 ], 'кол-во -', a[ 2 ][ 2 ], 'сумма -', a[ 2 ][ 3 ] next ? '======================================================================' [/pre2]
Dima: еще тест ;) [pre2] proc main local nfor:=1000000 local i local ms:={} local hms:={=>} local nsec nsec:=seconds() for i=1 to nfor aadd(ms,i) next ? (seconds()-nsec)*1000 //641 nsec:=seconds() for i=1 to nfor hms:=i next ? (seconds()-nsec)*1000 //36937 но если предварительно сделать (до заполнения массива) // hb_hAllocate( hms, nfor ) , тогда время 821 nsec:=seconds() ascan(ms,nfor) ? (seconds()-nsec)*1000 //31 nsec:=seconds() HB_HHASKEY(hms,nfor) ? (seconds()-nsec)*1000 //0 return [/pre2]
Pasha: Конечно, при использовании хеша добавление в него происходит медленнее, чем при добавлении элемента в массив. Это тоже самое, что добавлять записи в файл с индексом медленнее, чем в файл без индекса, так как в первом случае еще обновляется индекс. Выигрыш достигается затем при поиске по ключу. Еще к тому же AADD оптимизирован по выделению памяти, т.е. элементы в него добавляются не по одному. Хеш без такой оптимизации сильно ему проиграет. То, что настолько сильно, для меня сюрприз.
Dima: Есть такая функция aValues := hb_hValues( aHash ) Возвращает массив всех значений массива aHash А нет ли похожей которая возвращает массив значений с определенным ключиком ?
Pasha: Dima пишет: А нет ли похожей которая возвращает массив значений с определенным ключиком ? Так в хеш ключ может быть только в одном экземпляре. И значение может быть одно. Или надо выбрать массив по диапазону ключей ?
Dima: Pasha пишет: Или надо выбрать массив по диапазону ключей ? Да. Я не так выразился.
Pasha: Нет, увы, такой функции нет
Dima: Еще вопросец ;) [pre2] fmas:={} hmas:={=>} dbeval({|| hmas[recno()]:={kod_kl,kmcod,codn}}) fmas:=xxxx() как быстро заполнить массив fmas значениями ключей для kmcod==3 ? BM_DBSETFILTERARRAY(fmas) [/pre2]
Dima: Пока посетила только вот такая идея [pre2] use klient new hb_hAllocate( hmas, lastrec() ) dbeval({|| hmas[recno()]:={kmcod,codgr}}) // для kmcod==3 hb_hEval( hmas, {|key,sval,ind| if(sval[1]==3,aadd(fmas,key),)}) // при размере массива 700000 записей hb_hEval работает 530 мс , хочется что то побыстрее BM_DBSETFILTERARRAY(fmas) dbgotop() browse() [/pre2]
полная версия страницы