Форум: "Прочее";
Текущий архив: 2016.03.13;
Скачать: [xml.tar.bz2];
ВнизБыстрый поиск комбинации строк в массиве Найти похожие ветки
← →
sniknik © (2015-05-27 17:03) [160]> Я чаще сталкивался с тем, что заказчик не совсем представляет что и как ему нужно.
тут заказчик "местный бос", который по ходу развития ветки "зарубил" вполне годное, рабочее решение со словами "не нравится"... ну, я так думаю это показатель что и как он себе представляет ему нужно (у нас в конторе также кстати).
> никакой уникальности нет.
даже в ID? (строковый намекает...). если да, то считай его нет.
← →
sniknik © (2015-05-27 17:09) [161]кстати миллион это не много... серьезно, выборка миллиона это секунд 5, записать в локальную (акксесс) базу еще сек 20 - 30. 10 тыщь для обработки (джойнов/реплейсов) вообще не серьезно... а база/движок реально сделает все быстрее "велосипеда" как бы мы тут не изгалялись...
ИМХО, в дроблении/обработке кусками нет смысла. переложить (пусть каждый раз все) в локальную базу, + обработать в ней это 2-3мин. не должно быть проблемой.
← →
Eraser © (2015-05-27 17:17) [162]
> sniknik © (27.05.15 17:09) [161]
вы про локальную базу тут уже всю плешь проели. см. внимательно
> Юрий Зотов © (26.05.15 09:54) [71]
> > D.N. Polezhaev © (26.05.15 09:41) [68]
>
> > А какие проблемы с памятью?
>
> Да пустяк - при выполнении SELECT где-то в недрах сервера
> приложений возникает исключение Out of memory.
> :o)
← →
Юрий Зотов © (2015-05-27 17:37) [163]> Сергей Суровцев © (27.05.15 16:52) [159]
> То что в результирующую таблицу
1. Создание таблиц и представлений в БД запрещено, даже временных. На клиенте БД (которым является апп-сервер) можно создать таблицу в памяти, если хватит самой этой памяти.
> попадет первый попавшийся полный однофамилец
> из исходного миллиона устраивает?
2. Нет. Должны попасть все, у кого совпали ФИО (с учетом Ё-Е). То есть, если на входе есть Иванов Семен Петрович, а в БД таких 20 человек, то в результат должны попасть все 20 (причем, и СемЕны, и СемЁны).
> Других критериев отбора кроме ФИО нет?
3. Можно считать, что нет. Первичный отбор идет именно по ФИО. Получившийся в его результате первичный набор записей потом как-то обрабатывается и при обработке действительно учитываются другие критерии - но для сабжа это уже неважно. Важно получить этот самый первичный набор.
> Или в результирующую надо собрать и всех однофамильцев тоже?
См.п.п. 1 и 2.
← →
sniknik © (2015-05-27 17:49) [164]> см. внимательно
я это видел. и не верю... на миллионе записей всего, что-то не так делали, ИМХО, а вот access через свой исам возможно сделает либо так... либо по другому. там 1 запрос всего то будет, ошибиться трудно.
← →
sniknik © (2015-05-27 17:52) [165]а вот это
> На клиенте БД (которым является апп-сервер) можно создать таблицу в памяти
уже явный запрет на создание файлов/баз клиентом.
← →
Sha © (2015-05-27 18:23) [166]Допилил. Вроде работает.
На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
Время почти не зависит от того, как читаем: по частям или нет.
unit ZotovFIOForm;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo3: TMemo;
Memo1: TMemo;
Memo2: TMemo;
procedure Button1Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const
Kilo= 1000;
BaseLimit= 1000 * Kilo;
ListLimit= 10 * Kilo;
ReadLimit= 100 * Kilo;
function GenerateFio(i: integer): string;
begin;
Result:=Format("%.10d", [i]);
end;
//имитация наполнения базы
procedure GenerateBase(var Base: TStringList);
var
i, k: integer;
begin;
Base.Clear;
i:=0;
repeat;
inc(i);
if i mod 7<4 then begin;
if i mod 19=0 then k:=Random(50) else k:=0;
repeat;
Base.Add(GenerateFio(i));
dec(k);
until k<0;
end;
until Base.Count>=BaseLimit;
end;
//имитация создания списка искомых записей
procedure GenerateList(var List: TStringList);
var
i: integer;
begin;
List.Clear;
i:=0;
repeat;
inc(i,1+Random(200));
until List.Add(GenerateFio(i))>=ListLimit;
end;
//гарантируем отсутствие дубликатов в списке искомых записей
procedure DelDuples(var List: TStringList);
var
i: integer;
begin;
for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then List.Delete(i);
end;
//поиск записей List в базе одним куском
procedure FindFio1(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; BaseLeft, BaseRight: integer;
var Res: TStringList);
begin;
if BaseLeft<BaseRight then while true do begin;
if List[ListLeft]<Base[BaseLeft] then begin;
inc(ListLeft); if ListLeft>=ListRight then exit;
end
else begin;
if List[ListLeft]>Base[BaseLeft] then inc(BaseLeft)
else repeat;
Res.Add(Base[BaseLeft]); inc(BaseLeft);
until (BaseLeft>=BaseRight) or (Base[BaseLeft]<>List[ListLeft]);
if BaseLeft>=BaseRight then exit;
end;
end;
end;
//имитация SQL COUNT и SQL SELECT
procedure CountAndGet(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
if not Base.Find(ValueFrom, BaseLeft) then inc(BaseLeft)
else while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight) then begin;
inc(BaseRight);
if IncludeValueTo then while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end;
BaseCount:=BaseRight-BaseLeft;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList;
var Res: TStringList);
var
BaseLeft, BaseRight, BaseCount, IgnoreLeft, IgnoreRight, IgnoreCount, Current, Left, Right: integer;
Stack: array[0..31] of integer;
begin;
if ListLeft<ListRight then begin;
Current:=0; Stack[Current]:=ListRight;
Left:=ListLeft;
while Current>=0 do begin;
Right:=Stack[Current]; dec(Current);
while Left+1<Right do begin;
CountAndGet(List, Left, Right, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
if BaseCount<=ReadLimit then break;
inc(Current); Stack[Current]:=Right;
Right:=Left+(Right-Left) div 2;
end;
if BaseCount>0 then begin;
CountAndGet(List, Left, Right, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
FindFio1(List, Left, Right, Base, BaseLeft, BaseRight, Res);
end;
Left:=Right;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
Base, List, Fio1, Fio2: TStringList;
begin;
Base:=TStringList.Create;
List:=TStringList.Create;
Fio1:=TStringList.Create;
Fio2:=TStringList.Create;
try
Memo3.Lines.Add("generate...");
//RandSeed:=0;
Randomize;
GenerateBase(Base); Base.Sort;
GenerateList(List); List.Sort; DelDuples(List);
Memo3.Lines.Add("start...");
FindFio1(List, 0, List.Count, Base, 0, Base.Count, Fio1);
Memo3.Lines.Add("done FindFio1: "+IntToStr(Fio1.Count));
if Kilo<=10 then Memo1.Text:=Fio1.Text;
FindFio2(List, 0, List.Count, Base, Fio2);
Memo3.Lines.Add("done FindFio2: "+IntToStr(Fio2.Count));
if Kilo<=10 then Memo2.Text:=Fio2.Text;
finally
Base.Free;
List.Free;
Fio1.Free;
Fio2.Free;
end;
end;
end.
← →
Sha © (2015-05-27 21:33) [167]исправлен баг в процедуре CountAndGet:
//имитация SQL COUNT и SQL SELECT
procedure CountAndGet(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
if Base.Find(ValueFrom, BaseLeft)
then while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight)
then if IncludeValueTo
then begin;
inc(BaseRight);
while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end
else while (BaseRight>0) and (Base[BaseRight-1]=ValueTo) do dec(BaseRight);
BaseCount:=BaseRight-BaseLeft;
end;
← →
Sha © (2015-05-28 09:22) [168]В процедуре поиска по частям FindFio2 количество вызовов процедуры CountAndGet с целью подсчета размера части уменьшено примерно в 2 раза.
Попутно исправлена небольшая неточность.
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList;
var Res: TStringList);
type
TStack= record
Right, Size: integer;
end;
var
BaseLeft, BaseRight, BaseCount, IgnoreLeft, IgnoreRight, IgnoreCount, Current, Left, Right, Size: integer;
Stack: array[0..31] of TStack;
begin;
if ListLeft<ListRight then begin;
CountAndGet(List, ListLeft, ListRight, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
Current:=0; Stack[Current].Right:=ListRight; Stack[Current].Size:=BaseCount;
Left:=ListLeft;
while Current>=0 do begin;
Right:=Stack[Current].Right; Size:=Stack[Current].Size; dec(Current);
while (Size>ReadLimit) and (Left+1<Right) do begin;
inc(Current); Stack[Current].Right:=Right;
Right:=Left+(Right-Left) div 2;
CountAndGet(List, Left, Right, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
Stack[Current].Size:=Size-BaseCount;
Size:=BaseCount;
end;
if Size>0 then begin;
CountAndGet(List, Left, Right, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
FindFio1(List, Left, Right, Base, BaseLeft, BaseRight, Res);
end;
Left:=Right;
end;
end;
end;
← →
Игорь Шевченко © (2015-05-28 10:22) [169]Sha © (28.05.15 09:22) [168]
Как ты это читаешь - не понимаю
← →
Sha © (2015-05-28 11:55) [170]а я не читаю )
← →
Игорь Шевченко © (2015-05-28 11:58) [171]Sha © (28.05.15 11:55) [170]
Великолепно! Я верю, что твой код работает быстро, и даже очень быстро.
← →
Sha © (2015-05-28 12:23) [172]Игорь Шевченко © (28.05.15 11:58) [171]
На сам деле там есть "лишние" переменные, можно обойтись их меньшим числом, и есть что упростить. Например, имеет смысл разделить селект и каунт. Это всего лишь код, написанный за пару часов в перерывах между работой и совещаниями. Излишества и некрасивости - только для того, чтобы "оно почти работало". Даже не альфа-версия. Просто не падает при отладке. Нисколько не претендую на вылизанный код. Просто демонстрация идеи. А то тут не все слова иногда бывают понятны. Решил добавить кода. Дабы усугубить.
← →
MsGuns © (2015-05-28 12:29) [173]>На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
Огласите характеристики выч.системы (ПК), пжслт
← →
Sha © (2015-05-28 12:43) [174]> MsGuns © (28.05.15 12:29) [173]
>> На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
> Огласите характеристики выч.системы (ПК), пжслт
i5-3470 @ 3.2GHz, 4Gb
Приведено время работы процедур FindFio1 и FindFio2 при эмуляции COUNT/SELECT запросов к базе операциями в ОП. Чтобы получить реальное время работы на миллионе записей при максимальном размере части 10^5 записей, к этому времени надо добавить время выполнения примерно 10 COUNT и 10 SELECT. Кроме того, если SELECT возвращает несортированные записи, то надо добавить время сортировки записей в ОП.
← →
sniknik © (2015-05-28 13:04) [175]> Огласите характеристики выч.системы (ПК), пжслт
а смысл? "эмуляция" с позиционной(/локальной) логикой доступа, а ля "ValueTo:=List[ListRight];", вместо "клиент серверной" по данным, чем он показателен? да ничем.
или сомнения какие, что позиционное быстрее выбора по данным/условию (значение > чего-то, или меньше, пусть даже по индексу)? с указателями еще быстрее, а уж если оптимизатор выкинет расчеты как ни на что не влияющие, то будет вообще мгновенно на любом количестве...
> if Kilo<=10 then Memo1.Text:=Fio1.Text;
вот это вот условие оно же никогда не сработает вроде? значит вывода нет (проверить работу оптимизатора...).
← →
Sha © (2015-05-28 13:16) [176]> sniknik © (28.05.15 13:04) [175]
> "эмуляция" с позиционной(/локальной) логикой доступа, а ля "ValueTo:=List[ListRight];",
>вместо "клиент серверной" по данным, чем он показателен? да ничем.
Кому ничем, а кому говорит о том, что время работы алгоритма целиком определяется временем последовательного выполнения сервером БД 20-40 запросов. Т.е. алгоритм, в принципе, годен.
> или сомнения какие, что позиционное быстрее выбора по данным/условию...
че за бред
>> if Kilo<=10 then Memo1.Text:=Fio1.Text;
> вот это вот условие оно же никогда не сработает вроде?
> значит вывода нет (проверить работу оптимизатора...).
даже не думал, что тут возможны непонятки...
(подсказка: есть такое слово - отладка)
← →
MsGuns © (2015-05-28 13:28) [177]Для чистоты экперимента неплохо б прогнать тест на каком-нибудь целенончике с 500M ОЗУ.
← →
sniknik © (2015-05-28 14:11) [178]> че за бред
нормальный такой "бред"...
в общем то весь спор в том, что вам говорят - нельзя при работе сервером базы указывать позицию, говорить "дай мне с сотой по тысячную записи". нет там позиций. а вы пытаетесь это опровергнуть рассказывая, и теперь показывая как это можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком, где это все есть, и это никем не опровергалось.
← →
MsGuns © (2015-05-28 14:26) [179]Коля, я вообще не врубился как они хотят заменить выборку из базы с ФИО на какие-то "индексы" (ID).
← →
Sha © (2015-05-28 14:28) [180]> sniknik © (28.05.15 14:11) [178]
>> че за бред
> нормальный такой "бред"...
> в общем то весь спор в том, что вам говорят - нельзя при работе сервером базы указывать позицию,
> говорить "дай мне с сотой по тысячную записи". нет там позиций.
> а вы пытаетесь это опровергнуть рассказывая,
> и теперь показывая как это можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком, где это все есть,
> и это никем не опровергалось.
Не надоело?
Который по счету раз приписывать другому какую-то выдуманную хрень?
Нежелание понять чужую мысль просто зашкаливает.
Ты бы пример привел уже наконец, где обнаружил обращение к данным не по значению.
← →
Illusion © (2015-05-28 14:42) [181]Удалено модератором
← →
Eraser © (2015-05-28 14:52) [182]
> sniknik © (28.05.15 14:11) [178]
> нормальный такой "бред"...
> в общем то весь спор в том, что вам говорят - нельзя при
> работе сервером базы указывать позицию, говорить "дай мне
> с сотой по тысячную записи". нет там позиций. а вы пытаетесь
> это опровергнуть рассказывая, и теперь показывая как это
> можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком,
> где это все есть, и это никем не опровергалось.
где первоисточник этого условия? или я что-то пропустил?
← →
ухты © (2015-05-28 15:01) [183]Задача же "одноразовая", так чего тут думать? еще можно понять если эти запросы высоко-нагрузочные, а так ...
← →
kaif © (2015-05-28 17:58) [184]А нельзя на клиенте какую-нибудь человеческую базу данных поставить?
Маленькую...
Туда закачать в нормальном виде, сделав три колонки, индекс, и там искать...
← →
Sha © (2015-05-28 21:42) [185]попытался немного повысить читаемость: букв стало больше, результат остался тем же )
unit ZotovFIOForm;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Memo2: TMemo;
Memo3: TMemo;
Button1: TButton;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const
Kilo= 1000; //1..10000;
BaseLimit= 1000 * Kilo;
ListLimit= 10 * Kilo;
ReadLimit= 100 * Kilo;
function GenerateFio(i: integer): string;
begin;
Result:=Format("%.10d", [i]);
end;
//создание списка записей, среди которых будем искать (имитация БД)
procedure GenerateBase(var Base: TStringList);
var
i, k: integer;
begin;
Base.Clear;
i:=0;
repeat;
inc(i);
if i mod 7<4 then begin;
if i mod 19=0 then k:=Random(50) else k:=0;
repeat;
Base.Add(GenerateFio(i));
dec(k);
until k<0;
end;
until Base.Count>=BaseLimit;
end;
//создание списка искомых записей
procedure GenerateList(var List: TStringList);
var
i: integer;
begin;
List.Clear;
i:=0;
repeat;
inc(i,1+Random(200));
until List.Add(GenerateFio(i))>=ListLimit;
end;
//гарантируем отсутствие дубликатов в списке искомых записей
procedure DelDuples(var List: TStringList);
var
i: integer;
begin;
for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then List.Delete(i);
end;
//определение границ интервала для SQL SELECT и SQL COUNT
procedure ListIndexesToValues(List: TStringList; ListLeft, ListRight: integer;
var ValueFrom, ValueTo: string; var IncludeValueTo: boolean);
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
end;
//имитация SQL SELECT и SQL COUNT
procedure FakeSelectCount(const ValueFrom, ValueTo: string; IncludeValueTo: boolean;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
begin;
if Base.Find(ValueFrom, BaseLeft)
then while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight)
then if IncludeValueTo
then begin;
inc(BaseRight);
while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end
else while (BaseRight>0) and (Base[BaseRight-1]=ValueTo) do dec(BaseRight);
BaseCount:=BaseRight-BaseLeft;
end;
//определение количества записей в БД в заданном интервале значений
procedure SqlCount(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseCount: integer);
var
BaseLeft, BaseRight: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, BaseCount); //SQL COUNT HERE
end;
//выборка записей из БД в заданном интервале значений
procedure SqlSelect(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight: integer);
var
BaseCount: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, BaseCount); //SQL SELECT HERE
end;
//поиск записей из интервала List в интервале Base, найденные помещаются в Res
procedure FindFio(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; BaseLeft, BaseRight: integer;
var Res: TStringList);
begin;
if BaseLeft<BaseRight then while true do begin;
if List[ListLeft]<Base[BaseLeft] then begin;
inc(ListLeft); if ListLeft>=ListRight then exit;
end
else begin;
if List[ListLeft]>Base[BaseLeft] then inc(BaseLeft)
else repeat;
Res.Add(Base[BaseLeft]); inc(BaseLeft);
until (BaseLeft>=BaseRight) or (Base[BaseLeft]<>List[ListLeft]);
if BaseLeft>=BaseRight then exit;
end;
end;
end;
//поиск записей List в базе одним запросом
procedure FindFio1(List, Base: TStringList; var Res: TStringList);
var
ListLeft, ListRight, BaseLeft, BaseRight: integer;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List, Base: TStringList; var Res: TStringList);
type
TStack= record
Right, Count: integer;
end;
var
ListLeft, ListRight, PartCount, BaseLeft, BaseRight, BaseCount, Current: integer;
Stack: array[0..31] of TStack;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Current:=0;
Stack[Current].Right:=ListRight;
Stack[Current].Count:=BaseCount;
while Current>=0 do begin;
ListRight:=Stack[Current].Right;
PartCount:=Stack[Current].Count;
dec(Current);
while (PartCount>ReadLimit) and (ListLeft+1<ListRight) do begin;
inc(Current);
Stack[Current].Right:=ListRight;
ListRight:=ListLeft+(ListRight-ListLeft) div 2;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Stack[Current].Count:=PartCount-BaseCount;
PartCount:=BaseCount;
end;
if PartCount>0 then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
ListLeft:=ListRight;
end;
end;
end;
← →
Sha © (2015-05-28 21:42) [186]
procedure TForm1.Button1Click(Sender: TObject);
var
Base, List, Fio1, Fio2: TStringList;
Seed: integer;
begin;
Base:=TStringList.Create;
List:=TStringList.Create;
Fio1:=TStringList.Create;
Fio2:=TStringList.Create;
try
if Sender<>nil then Memo3.Lines.Add("generate...");
Randomize;
//RandSeed:=-2046000228;
Seed:=RandSeed;
GenerateBase(Base); Base.Sort;
GenerateList(List); List.Sort; DelDuples(List);
if Sender<>nil then Memo3.Lines.Add("start...");
FindFio1(List, Base, Fio1);
if Sender<>nil then Memo3.Lines.Add("done FindFio1: "+IntToStr(Fio1.Count));
FindFio2(List, Base, Fio2);
if Sender<>nil then Memo3.Lines.Add("done FindFio2: "+IntToStr(Fio2.Count));
if (Sender<>nil) or (Fio1.Count<>Fio2.Count) then begin;
if Fio1.Count<>Fio2.Count then Memo3.Lines.Add(Format("error: %d %d %d",[Seed, Fio1.Count, Fio2.Count]));
if Kilo<=10 then begin;
Memo1.Text:=Fio1.Text;
Memo2.Text:=Fio2.Text;
end;
end;
finally
Base.Free;
List.Free;
Fio1.Free;
Fio2.Free;
end;
end;
//testing
procedure TForm1.Button2Click(Sender: TObject);
var
i: integer;
begin;
//RandSeed:=-2046000228;
if Kilo<>1 then begin;
Memo3.Lines.Add("wrong kilo");
exit;
end;
for i:=1 to 10000 do begin;
Button1Click(nil);
if i mod 1000=0 then Memo3.Lines.Add(IntToStr(i)+" loops done");
end;
Memo3.Lines.Add("All loops done");
end;
end.
← →
Игорь Шевченко © (2015-05-28 23:11) [187]Sha © (28.05.15 21:42) [185]
> procedure DelDuples(var List: TStringList);
> var
> i: integer;
> begin;
> for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then
> List.Delete(i);
> end;
При всем уважении - зачем у параметра модификатор var ?
← →
ogs © (2015-05-28 23:45) [188]Удалено модератором
← →
Sha © (2015-05-29 02:12) [189]> Игорь Шевченко © (28.05.15 23:11) [187]
> ogs © (28.05.15 23:45) [188]
Как уже писал где-то выше, у этого кода одна цель - подкрепить идею, которую с переменным успехом пытался описать. Когда я (не особенно долго) думал над тем, какой выбрать тип для хранения данных, первая мысль была - это массив записей, содержащих строки и другую необходимую информацию (о буквах ё). Она базировалась на том, что, в принципе, весь код можно построить так, что в любой момент будет заранее известна результирующая длина такого массива, и можно будет работать с ним, в частности, удалять записи довольно быстро. Однако в этом случае код будет содержать ненужные для понимая основной идеи (о которой здесь и зашел спор) подробности этой самой организации, которые будут отвлекать внимание. Поэтому еще после некоторых размышлений победила идея простоты. Если вместо трех строк оставить одну, выкинуть ё-флаги, то можно будет использовать TStringList, у которого есть полезные и удобные в нашем случае вещи (Find, Grow, Delete), которые могут упростить код и сделать его прозрачнее, т.к., по-моему мнению, станет возможно обеспечить соответствие почти один-в-один между строкой текста и строкой кода. А если потом потребуется обсудить выкинутые детали - потом и обсудим, как изменить код под реальную задачу. Как раз для этого у параметров и оставлены маячки-модификаторы. Сейчас замедления это никакого не дает, зато потом может пригодиться. Это если говорить кратко. Относительно использования в примере TStringList были и другие соображения, менее заслуживающие упоминания.
← →
kaif © (2015-05-29 05:14) [190]Не хочу быть назойливым. Но наверняка в Java есть уже написанные движки маленьких баз данных, которые можно было бы использовать для решения подобных задач. Первое же, что попалось в гугле:
http://hsqldb.org/
HSQLDB (HyperSQL DataBase) is the leading SQL relational database software written in Java. It offers a small, fast multithreaded and transactional database engine with in-memory and disk-based tables and supports embedded and server modes.
Судя по тому, как автор сабжа хочет побольше разных идей, может стоит посвятить пару часов и копнуть в направлении подобных маленьких баз. Чтобы не изобретать велосипед на ровном месте. И не писать заново код всякий раз, когда заказчик попросит внести туда еще что-нибудь. Например, к каждому челу еще и дату его рождения.
← →
кгшзх © (2015-05-29 08:26) [191]вся ява вот и есть такая. точнее явосообщество.
"три биллионс девайсес ран ява"
"нас миллиарды, наверняка кто-то уже написал готовый класс за нас, надо его только найти"
и находят.
а потом мучительно сопрягают найденных ужей и ежей.
я-ву, я-ву взял я на ха-лявууууу.
← →
Sha © (2015-05-29 09:30) [192]Sha © (29.05.15 02:12) [189]
Тем не менее, помимо борьбы за чистоту параметров есть одна нереализованная оптимизация, которую давно держу в голове.
В реальной жизни на большом массиве искомых значений нам всегда удастся подобрать несколько элементов этого массива так, чтобы разбить все значения в БД на 10 примерно одинаковых по размеру частей. Но что делать, когда жизнь нереальная или массив маленький, или наоборот?
Подбирая размер части, мы каждый раз сдвигаем ее границы, пока в худшем случае не получим ListLeft+1=ListRight. Т.к. при этом мы считаем, что правая граница не входит в диапазон, то по-существу весь диапазон схлопнулся до однофамильцев из List[ListLeft]. И это можно учесть в запросе SELECT. Но было бы неверно учесть этот факт в запросе COUNT, т.к. это испортит статистику для следующей части. В таком случае встает вопрос, как быть, если мы хотим знать количество считанных записей заранее, скажем, чтобы выделить память? Т.к. эта ситуация, по идее, чрезвычайно редкая, и уж точно не возникнет более 10 раз за время работы алгоритма, то ничто не мешает нам пересчитать количество записей в диапазоне в этом редком случае, повторно выполнив COUNT, учитывающий текущее состояние вычислений.
← →
Игорь Шевченко © (2015-05-29 11:32) [193]
> Как раз для этого у параметров и оставлены маячки-модификаторы.
> Сейчас замедления это никакого не дает, зато потом может
> пригодиться.
var подразумевает, что значение переменной меняется в теле функции. Я изменения не увидел (другой List не подставился), поэтому и спросил.
← →
Sha © (2015-05-29 12:03) [194]Игорь Шевченко © (29.05.15 11:32) [193]
Разумеется. Так и должно быть.
Но var там окажется нужен, если мы вдруг захотим поменять тип параметра. Например, на массив записей.
← →
Sha © (2015-05-29 13:06) [195]Измененные с учетом [192] процедуры:
//выборка записей из БД в заданном интервале значений
procedure SqlSelect(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
IgnoreLeft, IgnoreRight, IgnoreCount: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
//учтем особый случай, когда диапазон схлопнулся до однофамильцев и однофамильцы находятся не в самом конце List
if (ListLeft+1=ListRight) and (ListRight<List.Count) then ListRight:=ListLeft;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
//пересчитаем COUNT в особом случае, если нам требуется предварительно уточнить количество записей в диапазоне
if ListLeft=ListRight
then FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
end;
//поиск записей List в базе одним запросом
procedure FindFio1(List, Base: TStringList; var Res: TStringList);
var
ListLeft, ListRight, BaseLeft, BaseRight, IgnoreCount: integer;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, IgnoreCount);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List, Base: TStringList; var Res: TStringList);
type
TStack= record
Right, Count: integer;
end;
var
ListLeft, ListRight, PartCount, BaseLeft, BaseRight, BaseCount, Current: integer;
Stack: array[0..31] of TStack;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Current:=0;
Stack[Current].Right:=ListRight;
Stack[Current].Count:=BaseCount;
while Current>=0 do begin;
ListRight:=Stack[Current].Right;
PartCount:=Stack[Current].Count;
dec(Current);
while (PartCount>ReadLimit) and (ListLeft+1<ListRight) do begin;
inc(Current);
Stack[Current].Right:=ListRight;
ListRight:=ListLeft+(ListRight-ListLeft) div 2;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Stack[Current].Count:=PartCount-BaseCount;
PartCount:=BaseCount;
end;
if PartCount>0 then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, PartCount);
if PartCount>0 then FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
ListLeft:=ListRight;
end;
end;
end;
← →
Jeer © (2015-05-30 18:17) [196]Шо интересно - Зотову это помогло или так, было за потрепаться?
← →
картман © (2015-05-30 21:56) [197]Индексы для хакеров))
← →
Inovet © (2015-05-30 22:33) [198]Я там где-то ещё в самом начале про мемори готовую тейбл говорил. Уж про целую СУБД не решился упомянуть, ибо как-то оно совсем неправильно. Но всяко может быть, как видим.
← →
Romkin © (2015-06-02 10:44) [199]Вот смотрю и думаю: из БД же можно взять отсортированные уже строки, пусть по частям и медленно. Отсортировать массив фио и за один проход слить с имеющимся в БД, выявляя равенство.
Не будет ли это достаточно быстро?
← →
Юрий Зотов © (2015-06-02 11:08) [200]> Romkin © (02.06.15 10:44) [199]
Вот такой запрос работает быстро:select ... from ... where
фамилия = :param1 and имя = :param2 and отчество = :param3
Но вся проблема в функциях. Как только в запрос включаем функции, начинаются тормоза:select ... from ... where
replace(upper(фамилия), "Ё", "Е") = :param1
and
replace(upper(имя), "Ё", "Е") = :param2
and
replace(upper(отчество), "Ё", "Е") = :param3
где параметры - это входные ФИО, соответственно подготовленные.
Страницы: 1 2 3 4 5 6 7 вся ветка
Форум: "Прочее";
Текущий архив: 2016.03.13;
Скачать: [xml.tar.bz2];
Память: 0.88 MB
Время: 0.028 c