| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Как оптимизировать скорость работы кода [D7, XP]
Kaer © (2008-06-10 13:08:00)При расчете если поставить 5000 очень долго(гдето больше 25 часов) идет проверка одинаковых значеный(выделено жирным), мож как нитьбудь это оптимизировать чтобы побыстрей проверялось?
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, shellapi, ComCtrls;
type
TForm1 = class(TForm)
Edit1: TEdit;
Button1: TButton;
Memo1: TMemo;
Edit2: TEdit;
CheckBox1: TCheckBox;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
x, y, a, b, i: integer;
a_2, b_2: int64;
ar: array of array of array of int64;
f,d,l: TextFile;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
Memo1.Lines.Clear;
AssignFile(d,'Пов_числа.txt');
ReWrite(d);
AssignFile(l,'Лог.txt');
ReWrite(l);
i:= StrToInt64(Edit1.Text);
SetLength(ar,i+1,i+1,3);
Writeln(l,TimeToStr(Time)+' - Запуск');
Memo1.Lines.Add(TimeToStr(Time)+' - Запуск');
//заполняю массив
for a := 1 to i do
for b := 1 to a do
begin
a_2:=a*a;
b_2:=b*b;
ar[b,a,0] := 2*a*b;
ar[b,a,1] := a_2*a_2-b_2*b_2;
ar[b,a,2] := a_2*a_2+b_2*b_2;
end;
Writeln(l,TimeToStr(Time)+' - Массив заполнен');
Memo1.Lines.Add(TimeToStr(Time)+' - Массив заполнен');
//Вывод таблицы
If CheckBox1.Checked then
begin
AssignFile(f,'Таблица.txt');
ReWrite(f);
for a:= 1 to i do
begin
for b:=1 to a do if b=a then Writeln(f, IntToStr(ar[b,a,0])) else Write(f, IntToStr(ar[b,a,0])+' ');
for b:=1 to a do if b=a then Writeln(f, IntToStr(ar[b,a,1])) else Write(f, IntToStr(ar[b,a,1])+' ');
for b:=1 to a do if b=a then Writeln(f, IntToStr(ar[b,a,2])) else Write(f, IntToStr(ar[b,a,2])+' ');
Writeln(f,' ');
end;
CloseFile(f);
Writeln(l,TimeToStr(Time)+' - Таблица сгененирована');
Memo1.Lines.Add(TimeToStr(Time)+' - Таблица сгененирована');
end;
//произвожу сравнение
Memo1.Lines.Add(TimeToStr(Time)+' - Начало сравнения значений');
for y := StrToInt(Edit2.Text) to i do
begin
for x := 1 to y do
begin
Memo1.Lines.Add(TimeToStr(Time)+' - Проверяется '+IntToStr(y)+' строка, '+IntToStr(x)+' столбец');
for a:= 1 to i do
for b:= 1 to a do
if (ar[x,y,1]=ar[b,a,2]) then
begin
Writeln(d, IntToStr(ar[x,y,1]));
Writeln(d,'Строка '+IntToStr(a)+' столбец '+IntToStr(b)+' - 3');
Writeln(d,'Строка '+IntToStr(y)+' столбец '+IntToStr(x)+' - 2');
Writeln(d,' ');
end;
end;
Memo1.Lines.Add(TimeToStr(Time)+' - '+FloatToStr(100/i*y)+'%');
end;
Memo1.Lines.Add(TimeToStr(Time)+' - Раcчет закончен');
CloseFile(d);
CloseFile(l);
end;
end.
Kaer (2008-06-11 17:32:00) [1]Забыл сказать, спасибо кто помогал, особенно MBo.
Kaer (2008-06-11 17:20:00) [2]
> ну и проходи практику на заводе, больше пользы принесешь
у меня практика заключается в создании этой программы(по возможности конечно). Я вижу дискуссия пошла в другую сторону от задуманной темой так что наверное, модератор, закройте её пожалуйста, буду сам разбираться. :(
Игорь Шевченко (2008-06-11 14:33:00) [3]
> блин мне 20 лет, у меня нет образования, я вооще практику
> на заводе прохожу, и там мне одна тетька дала мне это задание,
> которое ей самой надо было сделать для этого кандидата
ну и проходи практику на заводе, больше пользы принесешь
Anatoly Podgoretsky (2008-06-11 14:29:00) [4]Имя конечно красивая, а мне больше Антенна нравится.
Kaer (2008-06-11 13:41:00) [5]
> поскольку даже минимальное решение предложенными алгоритмами
> без привлечения длинной математики (что медленно) или теории
> чисел (что, возможно, позволило бы найти другие пути) не
> получить, есть предложение сделать программу, поторая будет
> неделю нагружать комп, а потом скажет - решений для чисел
> < 200 000 не имеется;)
эээээ.... чего? :-)
Поросенок Винни-Пух (2008-06-11 13:37:00) [6]какая наука дала кандидату?
MBo (2008-06-11 13:37:00) [7]поскольку даже минимальное решение предложенными алгоритмами без привлечения длинной математики (что медленно) или теории чисел (что, возможно, позволило бы найти другие пути) не получить, есть предложение сделать программу, поторая будет неделю нагружать комп, а потом скажет - решений для чисел < 200 000 не имеется
;)
Kaer (2008-06-11 13:36:00) [8]Нет, не так. Какая наука дала возможности кандидату, такими он и пользуется.
Anatoly Podgoretsky (2008-06-11 13:24:00) [9]> Kaer (11.06.2008 13:05:24) [24]
Какой кандидат, такая и тетка, такой и "программист", соответственно такая же и наука.
Kaer (2008-06-11 13:05:00) [10]
> > > O(n^2)это вобще что?мдяи этот чел что-то там алгоритмизирует.
> .. для кандидата...бедная наша наука...
блин мне 20 лет, у меня нет образования, я вооще практику на заводе прохожу, и там мне одна тетька дала мне это задание, которое ей самой надо было сделать для этого кандидата, я его даже в глаза не видел, так что наука мож и бедная но явно не из-за меня :-)
MBo (2008-06-11 12:56:00) [11]for a := 1 to i do
for b := 1 to a do
begin
Diff[ a].Res:=a*a*a-b*b*b;
для индекса нужна другая переменная, а длина массивов будет i *(i+1)/2
Правильный_Вася (2008-06-11 11:03:00) [12]
> > O(n^2)это вобще что?
мдя
и этот чел что-то там алгоритмизирует... для кандидата...
бедная наша наука...
Kaer (2008-06-11 10:52:00) [13]делаю вот так
type
Data = record
Res: Int64;
A, B: Integer;
end;
...
var
Form1: TForm1;
Diff, Summ: array of Data;
a,b,i: integer;
...
SetLength(Diff,i+1);
SetLength(Summ,i+1);
for a := 1 to i do
for b := 1 to a do
begin
Diff[a].Res:=a*a*a-b*b*b;
Diff[a].A:=a;
Diff[a].B:=b;
Summ[a].Res:=a*a*a+b*b*b;
Summ[a].A:=a;
Summ[a].B:=b;
end;
А дальше не соображу, после сортировки Diff[1].Res и Summ[1].Res должны же быть минимальны, а Diff[5000].Res и Summ[5000].Res максимальны? Если да, то тогда дальше что-то вроде этого?
a:=1;
b:=1;
repeat
if (Diff[a].Res>Summ[b].Res) then
b:=b+1
else if (Diff[a].Res<Summ[b].Res) then
a:=a+1
else if (Diff[a].Res=Summ[b].Res) then
begin
//Вывод
end;
until (a=5000) or (b=5000);
Kaer (2008-06-11 10:18:00) [14]
> MBo ©
хочу попробывать сделать
>Заводятся 2 массива структур Summ и Diffrecord
> Res: Int64; A, B: Integer;endRes - сумма или разность
> A и B в степеняхДалее сортировка массивов по полю ResЗатем
> делается один проход по обоим массивам одновременно. Индексы
> ставятся в начало.Если Res больше у очередного элемента
> первого массива, увеличивается индекс для второго массива
> и наборот.
тока не соображу как оперировать с массивом структур
MBo (2008-06-11 09:00:00) [15]n - размер задачи, максимальное число, возводимое в степень (в твоем коде - i)
O(n^2) означает, что количество операций пропорционально квадрату размер задачи
Kaer (2008-06-11 08:29:00) [16]
> O(n^2)
это вобще что?
> O(N^2*LogN)
и вот это тоже? ;-)
MBo (2008-06-11 06:22:00) [17]Алгоритм с лучшей вычислительной сложностью O(n^2) ценой увеличения затрат памяти.
Заводим 4 миллиарда файлов, в каждом по 4 миллиарда записей (A;B), позиция пары в этом гипермассиве A,B есть разность их степеней (pigeonhole принцип). Сортировка не требуется. Далее генерируются суммы и проверяется наличие в соотв. ячейке гипермассива.
;)
Kaer (2008-06-10 18:35:00) [18]Удалено модератором
Kaer (2008-06-10 18:35:00) [19]мммм.... ясно :-)
MBo (2008-06-10 18:27:00) [20]Гипотеза Эйлера - диофантово уравнение 4-й степени a^4+b^4+c^4=d^4 не имеет решений в целых числах (похоже на теорему Ферма)
Лет 30 назад все-таки доказали, что решений бесконечно много, минимальное я привел, и оно уже в Int64 не влазит, а в остальных фигурируют числа еще больше Параметрического уравнения для генерации решений не существует (неизвестно).
| |
Страницы: 