Отправлено: 23.01.10 23:35. Заголовок: Вопрос конечно интер..
Вопрос конечно интересный, ключевые слова: Верченко Андрей пишет:
цитата:
желательно красивую !
. В моем понимании красота в программировании, это - простота, целесообразность и надежность. Исходя из этих критериев, самое простое, целесообразное и надежное - функцией dbcreate создать dbf файл с двумя полями, первое поле тип character(10), второе numeric(10) индексированный по первому полю и записать весь массив в базу преобразовав первый элемент каждого подмассива в строку функцией str, затем вернуться на начало базы и просканировав ее функцией dbeval сформировать результирующий массив. Задача похожа на проверку! // Программа
LOCAL aDim, aNewDim := {}, aSubDim aDim := {{2000, 1}, {2009, 1}, {2009, 1}, {2008, 1}, {2000, 1}, {2008, 1}, {2003, 1}, {2009, 1}} DBCREATE("test", {{"key", "C", 10, 0}, {"count", "N", 10, 0}}) USE test INDEX ON key TO test UNIQUE AEVAL(aDim, {|x|IIF(!DBSEEK(STR(x[1])), (DBAPPEND(), FIELD->key := STR(x[1])), NIL), FIELD->count += x[2]}) DBEVAL({||aSubDim := {}, AADD(aSubDim, VAL(key)), AADD(aSubDim, count), AADD(aNewDim, aSubDim)}) CLOSE ERASE ("test.dbf") ERASE ("test.ntx") AEVAL(aNewDim, {|x|QOUT(x[1], x[2])}) ?
Отправлено: 24.01.10 03:52. Заголовок: Нарушается самый главный принцип - БЫСТРОДЕЙСТВИЕ !!!
Уважаемый Андрей !!! Как раз приведенное мной решение - САМОЕ БЫСТРОДЕЙСТВУЩЕЕ. Вы не застали время компьютеров AT/286 с тактовой частотой CPU 16 МГц. Только чтобы проверить это исходный массив должен быть ОЧЕНЬ БОЛЬШИМ (в идеале максимум - 4096 элементов) и компьютер - очень медленным (AT/286). И тогда Вы убедились бы в том, что программа с файлами работает мгновенно, а с вызовом ASCAN() - ЧАСЫ !!! Еще один вариант решения - САМОЕ КЛИППЕРОВСКОЕ !!!
// Программа
LOCAL aDim, aNewDim := {} aDim := {{2000, 1}, {2009, 1}, {2009, 1}, {2008, 1}, {2000, 1}, {2008, 1}, {2003, 1}, {2009, 1}} DBCREATE("test", {{"key", "N", 10, 0}, {"count", "N", 10, 0}}) USE test INDEX ON key TO test AEVAL(aDim, {|x|DBAPPEND(), FIELD->key := x[1], FIELD->count := x[2]}) TOTAL ON key FIELDS count TO test2 USE ERASE ("test.dbf") ERASE ("test" + INDEXEXT()) USE test2 DBEVAL({||AADD(aNewDim, {key, count})}) USE ERASE ("test2.dbf") AEVAL(aNewDim, {|x|QOUT(x[1], x[2])}) ?
// Результат
2000 2 2003 1 2008 2 2009 3
Почему предложенное решение - САМОЕ БЫСТРОДЕЙСТВУЮЩЕЕ? Потому что оно - ЛИНЕЙНО зависимо от числа элементов массива, а решение с использованием ASCAN - экспоненциально зависимо. То есть в моем решении время выполнения программы рассчитывается по формуле: N * M (где M - меньше 10), а в решении с ASCAN по формуле: N * N (то есть N в квадрате), если N = 4096, то какое число больше N * 10 или N в квадрате?
Почему предложенное решение - САМОЕ БЫСТРОДЕЙСТВУЮЩЕЕ? Потому что оно - ЛИНЕЙНО зависимо от числа элементов массива, а решение с использованием ASCAN - экспоненциально зависимо.
Это неверно. Вы сравниваете 2 разных алгоритма. Отсортируйте исходный массив, и затем обрабатывайте его в цикле без ASCAN линейно. И насчет быстродействия тоже неверно. Какие бы медленные не были бы АТ286, дисковые операции на них так же были очень медленными, так что неэффективное решение с ASCAN все равно отработает быстрее, чем запись на диск. ASCAN работает достаточно быстро Я использую работу с большими многомерными массивами с тысячами элементов как раз с тех времен, даже не 286, а 8086, и все работает достаточно быстро. Ниже я даю как раз фунцкции, написанные еще а начале 90-х, когда появился 5.01. Я их конечно многократно дорабатывал, но основа осталась с времен 8086 и "покоренья Крыма"
Function AADDQS(aArray, xValue, aD, aI) // ------------------------------------------------------------- // Аналог AADDQ. // Подразумевается, что входной поток поступает в отсортированном // порядке, т.е. проверяется совпадение только на последний // элемент. // ------------------------------------------------------------- Return AADDQ(aArray, xValue, aD, aI, .t.)
Function AADDQ(aArray, xValue, aD, aI, lSort) // ------------------------------------------------------------- // Аналог AADD - добавляет уникальный элемент в массив // Параметры: // aArray - исходный массив; // xValue - добавляемое значение (допускается массив); // [aD] - описывает добавляемый массив: // <1> - этот элемент используется для сравнения; // <2> - соответствующий элемент суммируется (default). // <3> - соответствующий элемент добавляется в подмассив (default); // <4> - подмассив добавляется уникально (рекурсия); // <5> // <6> - элементы подмассива суммируются; // <7> - подмассив добавляется уникально AADDQS (рекурсия); // <10> - расчитывается максимальное число; // <11> - элемент переприсваивается. // По умолчанию сравнение производится по 1-му элементу, // все числовые элементы суммируются, все массивы // добавляются. // lSort - исходный массив отсортирован. // Возвращает номер элемента массива. // ------------------------------------------------------------- Local nPos, nComp, aTemp, aComp, nC := 0, nP, ap, x Local nCount, lad := .t.
if IsArray(xValue)
if aD == nil /* проверить ! if aI == nil .and. lSort == nil Return HB_AADDQ(aArray, xValue) endif */ lad := .f. nCount := Len(xValue) /* aD = Array(nCount) aD[1] := 1 for nComp := 2 to nCount x := xValue[nComp] if IsNumber(x) aD[nComp] := 2 elseif IsArray(x) aD[nComp] := 3 // xValue[nComp] := AClone(xValue[nComp]) else aD[nComp] := 0 endif next // nC := nP := 1 */ else nCount := Len(aD) endif
// if nP == nil if lad aComp := Array(nCount) endif for nComp := 1 to nCount if lad .and. aD[nComp] == nil Loop elseif if(lad, aD[nComp] == 1, nComp == 1)
#ifndef __HARBOUR__ if ! lad if nComp # 1 x := xValue[nComp] if IsNumber(x) ap[nComp] += x elseif IsArray(x) AEval(x, {|a| AADD(ap[nComp], a)}) endif endif
Function AddNtoA(a, n, nInd) // ------------------------------------------------------------- // Суммирует параметр n к элементу nInd массива a // При необходимости создает, изменяет размерность // и иницализирует массив a // Возвращает: массив a // ------------------------------------------------------------- if nInd > 0 if a == nil a = Array(nInd) AFill(a, 0) a[nInd] = n elseif Len(a) < nInd ASize(a, nInd) a[nInd] := n else if a[nInd] == nil a[nInd] := n else a[nInd] += n endif endif elseif a == nil a = {} endif Return a
Function AddAr(a1, a2) // ------------------------------------------------------------- // Поэлементно прибавляет массив a2 к массиву a1 // При необходимости изменяет размерность и иницализирует массив a // ------------------------------------------------------------- Local i, nLen := len(a2) if len(a1) < nLen ASize(a1, nLen) endif for i = 1 to nLen if IsNumber(a2[ i ]) if a1[ i ] == nil a1[ i ] := a2[ i ] else a1[ i ] += a2[ i ] endif endif next Return nil
Function ASUM(aArray) // ------------------------------------------------------------- // Суммирует массив числового или символьного типа // ------------------------------------------------------------- Local xValue if ! Empty(aArray) xValue = aArray[1] AEVAL(aArray, {|xE| xValue += xE}, 2) else xValue = 0 endif Return xValue
Function AASUM(aArray, ax) // ------------------------------------------------------------- // Поэлементно суммирует массив числового или символьного типа // ------------------------------------------------------------- Local ser
for ser = 1 to len(ax) if ax[ser] # nil aArray[ser] += ax[ser] endif next Return nil
Function AADDA(a1, a2) // ------------------------------------------------------------- // Добавляет все элементы массива a2 к массиву a1 // Возвращает ссылку на массив a1. // ------------------------------------------------------------- if a1 == nil a1 := {} endif #ifndef __HARBOUR__ AEVAL(a2, {|a| AADD(a1, a)}) #else AMERGE(a1, a2) #endif Return a1
Function ADELM(a, n) // ------------------------------------------------------------- // Удаляет элемент n массива a и корректирует его размер // ------------------------------------------------------------- #ifndef __HARBOUR__ ADEL(a, n) ASize(a, len(a) - 1) Return a #else #ifdef __XHARBOUR__ Return ADEL(a, n, .t.) #else Return HB_ADEL(a, n, .t.) #endif #endif
Function ASortA(a, n, n2) // ------------------------------------------------------------- // Сортирует двухмерный массив по индексу n // Если задан n2 - сортировка по двум индексам // ------------------------------------------------------------- Return ASort(a,,, if(n2 == nil,; {|x1, x2| x1[n] < x2[n]},; {|x1, x2| if(x1[n]=x2[n], x1[n2]<x2[n2], x1[n]<x2[n])} ))
Function AInsM(a, n, x) // ------------------------------------------------------------- // Вставляет в массив a значение x в позицию n // ------------------------------------------------------------- #ifndef __HARBOUR__ AADD(a, nil) AINS(a, n) a[n] = x Return a #else #ifdef __XHARBOUR__ Return AINS(a, n, x, .t.) #else Return HB_AINS(a, n, x, .t.) #endif #endif
Function AEvalF(aRr, block, bFilter) // ------------------------------------------------------------- // Выполняет блок кода block для каждого элемента массива aRr, // удовлетворяющего фильтру bFilter // ------------------------------------------------------------- Local ser, a #ifndef __HARBOUR__ for a :=1 to len(aRr) #else for each a in aRr #endif if Eval(bFilter, a) Eval(block, a) endif next Return aRr
Function AFillA(a, x) // ------------------------------------------------------------- // Аналог aFill для подмассивов // ------------------------------------------------------------- Local ser for ser = 1 to len(a) if IsArray(a[ser]) AFillA(a[ser], x) elseif a[ser] == nil a[ser] := x endif next Return nil
// Добавлено 24.6.99 - лажа в макросах
Function ArrayGet(a, ni1, ni2, ni3) Local x if ni3 # nil x := a[ni1][ni2][ni3] elseif ni2 # nil x := a[ni1][ni2] else x := a[ni1] endif Return x
Function ArrayPut(a, x, ni1, ni2, ni3) if ni3 # nil a[ni1][ni2][ni3] := x elseif ni2 # nil a[ni1][ni2] := x else a[ni1] := x endif Return nil
Function ArrayInc(a, x, ni1, ni2, ni3) if ni3 # nil a[ni1][ni2][ni3] += x elseif ni2 # nil a[ni1][ni2] += x else a[ni1] += x endif Return nil
#ifndef __HARBOUR__
Function AScanA(a, x, n, lEqu) // ------------------------------------------------------------- // Поиск в двухмерном массиве a значения x по индексу n // lEqu - точный поиск строки // ------------------------------------------------------------- Return AScan(a, if(lEqu==nil, {|ax| ax[n] = x}, {|ax| ax[n] == x}))
Function AScanB(a, x, n, lEqu) // ------------------------------------------------------------- // Тоже самое, возвращает найденный массив // ------------------------------------------------------------- Local nPos := AScanA(a, x, n, lEqu), aRet if nPos # 0 aRet := a[nPos] endif Return aRet
Function AScanM(a, af) // ------------------------------------------------------------- // Поиск в двухмерном массиве a по массиву af // Сравниваются непустые элементы массива af. // ------------------------------------------------------------- Local ax, ser, i, l := .f.
Local as := {}, ay if ! Empty(a) for i := 1 to len(af) if i <= len(a[1]) .and. af[ i ] # nil AADD(as, {i, af[ i ]}) endif next endif //Return ASCAN(a, {|ax| doAScanM(ax, as)})
#ifndef __HARBOUR__ for ser := 1 to len(a) ax := a[ser] #else for each ax in a #endif l := .t.
// for i = 1 to len(af) // if len(ax) >= i .and. af[ i ] # nil .and. ! (ax[ i ] == af[ i ]) // l := .f. // Exit // endif // next
for each ay in as index i if ! (ax[ay[1]] == ay[2]) l := .f. exit endif next
if l #ifdef __HARBOUR__ ser := hb_EnumIndex() #endif Exit endif next Return if(l, ser, 0)
/* Static func doAScanM(ax, as) Local l := .t., ay for each ay in as index i if ! (ax[ay[1]] == ay[2]) l := .f. exit endif next Return l */
Function ASUMA(aArray, nPos) // ------------------------------------------------------------- // Суммирует элементы двумерного массива числового типа по 2-й размерности nPos // Возвращает: сумму // ------------------------------------------------------------- Local nSum := 0 AEval(aArray, {|a| nSum += a[nPos]}) Return nSum
Отправлено: 24.01.10 12:04. Заголовок: Я в свое время тоже ..
Я в свое время тоже работал с большими массивами, причем размер в 4096 преодолевал с помощью вложенных подмассивов (в Harbour слава богу это ограничение пропало). Так вот во времена "покорения Крыма" тормоза начинались, когда массив переставал помещаться в памяти и свопился на диск.
Отправлено: 24.01.10 21:26. Заголовок: Pasha пишет: Это не..
Pasha пишет:
цитата:
Это неверно. Вы сравниваете 2 разных алгоритма. Отсортируйте исходный массив, и затем обрабатывайте его в цикле без ASCAN линейно.
Что то я не пойму - Вы предлагаете при каждом добавлении в новый массив его сортировать, каким позвольте полюбопытствовать методом - методом "пузырька"? Тогда Ваша программа будет выполняться не часы, а ДНИ! И вообще спор бесполезный - в современных супер компьютерных системах с виртуальной памятью и кэшированием дисковых операций - сказать НАВЕРНЯКА что и когда будет записано на диск, то ли dbf файл, то ли страница виртуальной памяти с массивом НЕВОЗМОЖНО. Просто ПОВЕРЬТЕ на слово - команды INDEX ON и TOTAL ON - это САМЫЙ МОЩНЫЙ ИНСТРУМЕНТ xBase систем (и самый эффективный). И если, как я предполагаю, это было учебное задание Андрея, то можно узнать у него - что ему поставили преподаватели и за какой вариант (вроде третейского суда :-)
Что то я не пойму - Вы предлагаете при каждом добавлении в новый массив его сортировать, каким позвольте полюбопытствовать методом - методом "пузырька"? Тогда Ваша программа будет выполняться не часы, а ДНИ!
Конечно нет. Сначала формируется исходный массив (AADD), затем он сортируется (ASORT, один вызов), и затем формируется выходной массив
цитата:
И вообще спор бесполезный - в современных супер компьютерных системах с виртуальной памятью и кэшированием дисковых операций - сказать НАВЕРНЯКА что и когда будет записано на диск, то ли dbf файл, то ли страница виртуальной памяти с массивом НЕВОЗМОЖНО. Просто ПОВЕРЬТЕ на слово - команды INDEX ON и TOTAL ON - это САМЫЙ МОЩНЫЙ ИНСТРУМЕНТ xBase систем (и самый эффективный). И если, как я предполагаю, это было учебное задание Андрея, то можно узнать у него - что ему поставили преподаватели и за какой вариант (вроде третейского суда :-)
На слово не поверю :) То, что используется виртуальная память и кеширование файловых операций не означает, что хранение данных в памяти и в файле на диске равнозначны. К тому же, в нашем случае, еще будет задействована подсистема rdd. dbTotal (команда TOTAL) рудимент клиппера. Гляньте, как она реализована в харборе. Вы удивитесь :) через те же массивы. С тех пор, как она реализована (уже 10 лет как!) никому не пришло в голову ее переписать на С. Так что запись файла dbf - просто лишнее промежуточное действие. Даже есть использовать memarea, слой rdd будет выполнять операции медленне, чем обращение к элементам массива А использование индексации предполагает вызов dbSeek, а это поиск в индексном файле с его сложной страничной структурой И зачем это все, когда действия с массивами - это практически мгновенные операции со структурой item Любая операция с массивом даже не на порядок быстрее соответсвующего вызова rdd: AADD - dbAppend, Ascan - dbSeek
Из своего опыта. Посмотрите мою функцию ASCANM: реализацию в prg и на С Как-то я обнаружил, что эта функция очень тормозит при поиске в большом массиве. Оптимизировать ее на уровне prg уже некуда, и я переписал ее на С, и скорость ее работы увеличилась примерно в 100 раз, задержка просто исчезла. То есть, для оптимизации огромный эффект дает отказ от пи-кода и использования vm, несмотря на то, что vm оптимизировалась и вылизывалась многие годы, и кодирование критичного алгоритма на С
Конечно нет. Сначала формируется исходный массив (AADD), затем он сортируется (ASORT, один вызов), и затем формируется выходной массив
Если Вы предлагаете сразу же первой операцией сортировку исходного массива, то в принципе это ничем не отличается от индексирования и здесь можно до посинения приводить кучу аргументов как за так и против ЛЮБОГО решения. Если уж Си-код настолько эффективней пи-кода, тогда не проще ли вообще программировать на Си? Для систем с виртуальной памятью - это самое правильное - примитивнейшие алгоритмы и супер оптимизированный машинный Си-код. Но мы то в разделе CLIPPER!!! И отличия конкретной реализации в [x]Harbour RTL мне кажется здесь ни при чем. Pasha пишет:
цитата:
dbTotal (команда TOTAL) рудимент клиппера. Гляньте, как она реализована в харборе. Вы удивитесь :) через те же массивы. С тех пор, как она реализована (уже 10 лет как!) никому не пришло в голову ее переписать на С.
Глянул! Она (функция dbTotal) реализована и в Clipper-e и в [x]Harbour-e ОДИНАКОВО и массивы в ней используются для имен полей (массив из 1-го элемента) и сумм этих полей (массив тоже из 1-го элемента в нашем примере). Я ПОДЧЕРКИВАЮ - мое решение (с TOTAL ON) будет ЭФФЕКТИВНЕЙ в Clipper 5.01 на CPU 80286 16 МГц с 640 Кб RAM !!!
Слушайте, хватит спорить... Если кто-то хочет доказать свою правоту, то он берет и делает ТЕСТы того (массив) и другого (файл) примера ! Я не силен в доказательствах по научному, я просто практик. И я ответственно заявляю дисковые операции - ТОРМОЗА на всех процессорах от 8086 до сегодняшних. Я задачу еще делал в 2000 году на Клипере 5.3b, начисление абонентской платы по базе в 100 000 абонентов. Сделал самое простое в лоб - считывание прихода 1-БД, запись в файл DBF - врем.файл, расчет, запись расчета в 1-БД. Задача считалась по 12 часов !!! Это на 2-ом Pentium'е . Достало через год, переписал через массив - стал считать за 3 часа ! Сейчас на хХарборе за 1 час где-то, но по большому счету запись расчета в Базу - сильно тормозит расчеты.
А пример не в качестве задания, а тут дурацкие СБЕРБАНКОВСКИЕ файлы подкинули, вот и делал конвертор на МиниГуи... А алгоритм он и в Африке - алгоритм... Спасибо большое за подсказку....
Все даты в формате GMT
3 час. Хитов сегодня: 210
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет
- участник сейчас на форуме
- участник вне форума