Тестирование... на знание

← →
ferr © (2007-04-10 19:27) [80]

Съехало, есть основания полагать что из-за DMClient"а, ибо в блокноте всё было замечательно.

← →
ferr © (2007-04-10 19:32) [81]

Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761 Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936 Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436 Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597 InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466 QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100 QuickSortO 0.0016 0.0040 0.0092 0.0210 0.0468 0.1000 0.2250 0.4910 1.0600 2.2800 4.8700 10.410 23.270 HeapSort 0.0027 0.0061 0.0136 0.0305 0.0678 0.1493 0.3261 0.7000 1.5400 3.3800 7.4100 15.930 37.570 MergeSort 0.0015 0.0042 0.0104 0.0251 0.0571 0.1290 0.2871 0.6339 1.3996 3.0379 6.9225 15.633 35.464
Попробую ещё разок вставить, через вебформу.

← →
ferr © (2007-04-10 19:35) [82]

Премного перед всеми извиняюсь, особенно перед DMClient"ом ;-). Сам дурак.

P.S. Хотел лишь показать что BubbleSort самый медленный..

← →
IA (2007-04-10 19:40) [83]

Две ошибки, как уже сказано выше многократно, это

просто неправильный код, который приведет к AV. Ну а count или count -1, и Delete(i) это уже не существенно, считаем как одну. Вторая - это проверка на nil, человек который такое не заметил или "переписал" с list.Clear() на позицию выше начального уровня не годится, по-моему. В принципе, красиво - первая отсекает чайников, а вторая - кодеров.

← →
IA (2007-04-10 19:47) [84]

> P.S. Хотел лишь показать что BubbleSort самый медленный.
> .

Хм. А для этого надо тесты проводить? К тому же выводы у вас неправильные. Идите перечитывайте Кнута.

← →
ferr © (2007-04-10 19:53) [85]

> Хм. А для этого надо тесты проводить?

Нет, тесты я проводил для сравнения логарифмических методов.

> К тому же выводы у вас неправильные.

С этого места попрошу поподробнее. Я вроде и выводов-то никаких не делал..

> Идите перечитывайте Кнута.

Предлагаю обойтись без взаимопосылательства.

← →
IA (2007-04-10 19:58) [86]

> > К тому же выводы у вас неправильные.
>
> С этого места попрошу поподробнее. Я вроде и выводов-то
> никаких не делал..

Да? А это что?

> P.S. Хотел лишь показать что BubbleSort самый медленный

"На тестированном объеме и структуре данных". В ВУЗах уже не учат не делать глобальные выводы из частного случая?

>> Идите перечитывайте Кнута.

>Предлагаю обойтись без взаимопосылательства.

Ничего личного, но вам действительно надо почитать Кнута. Я даже сделал допуск что вы его уже читали.

← →
ferr © (2007-04-10 20:28) [87]

> Да? А это что?
>
> > P.S. Хотел лишь показать что BubbleSort самый медленный
>
> "На тестированном объеме и структуре данных". В ВУЗах уже
> не учат не делать глобальные выводы из частного случая?

Пожалуй и соглашусь, и не соглашусь. Я преподнёс это как пример, а не как эксперимент, не углубляясь в детали. Я мог бы углубить описания и специализировать выводы, но не стал, ибо незачем. А раз дополнительно ничего не написано, то значит рассматривается общая ситуация(случайный вход). Следовательно от алгоритма ожидается среднее время работы.

← →
Loginov Dmitry © (2007-04-10 20:32) [88]

> найдите ошибку в коде:
> procedure ClearList(List: TList);
> var
> I: Integer;
> begin
> for I:=0 to List.Count do
> List.Delete(I);
> end;

На самом деле задание очень простое (в данном случае все ошибки выявились за пол-сукунды). Имхо, лучше чтобы было примерно так:

procedure ClearList(List: TList); var I: Integer; begin for I:=0 to List.Count do begin List.Delete(I); Dispose(List[I]); end; end;

Сколько тут ошибок? :)
Здесь уж соискателям действительно мало шансов :)

А вот отсутствие проверки Assigned(List), имхо, не является ошибкой.

← →
MsGuns © (2007-04-10 21:26) [89]

Короче, воин, который не знает, что такое "дао вэнь линь" - не джидай.

← →
Eraser © (2007-04-10 21:43) [90]

Автоматически написал бы через downto, т.к. на практике, когда появляется похожая задача, обычно нужно удалять не все элементы, то только некоторые, согласно какому-то условию, в этом случае, downto более читабелен, imho.

← →
IA (2007-04-10 22:06) [91]

> А вот отсутствие проверки Assigned(List), имхо, не является
> ошибкой.

Разумеется. А потом ищи где у юзера AV выскочило. Проверка аргументов должна быть во всех public & protected методах, и в private зачастую. Что делать если аргумент пустой, кидать ошибку или молча обходить зависит от конкретного случая.
Собственно, наличие подобного кода один из различительных признаков между профессиональным разработчиком и кодером на коленке.

← →
Loginov Dmitry © (2007-04-10 22:42) [92]

> [91] IA (10.04.07 22:06)

Очень и очень сильно зависит от ситуации. Если по контексту задачи в функцию ClearList() не может попасть нулевая или битая ссылка, то НЕ стоит делать подобных проверок. Если по контексту задачи допускается передача в функцию нулевого указателя, то проверка нужна.

> Проверка аргументов должна быть во всех public & protected
> методах

Опять же, сильно зависит от ситуации. Часто бывает, что лучше выкинуть ошибку.

← →
vasIZmax © (2007-04-10 23:08) [93]

Итак, некоторые итоги:
для проверки логики (точнее писать алгоритмы, программирование как ни как на алгоритмах строится) - рекомендовано использовать сортировки. (более подробно пост MBo © в [32]).

Так же немало важным считаю и

> Проверить может ли класс от объекта отличить.
,
все это хорошо, но теорию тож надо знать/понимать/(уметь) объяснить.

Ну и проверка на понимание/способность читать/корректировать чужой код/переработка и усовершенствование.

Вот получается основные критерии. Но, это имхо.

ЗЫ. Честно говоря думал "задания" будут "по легче": ну там компонентик наваять, или запросик сделать в БД, или что-нибудь с графикой - хотя это конечно же зависит от специализации).

ЗЫЫ. Не ошибся ли я с такими выводами?

← →
Mystic © (2007-04-11 02:03) [94]

Если вопрос по алгоритмам, могу попросить решить какую-то задачу... Например, максимально быстро получить список всех ходов в шахматах/шашках.

← →
TUser © (2007-04-11 06:32) [95]

> > procedure ClearList(List: TList);
> > var
> > I: Integer;
> > begin
> > for I:=0 to List.Count do
> > List.Delete(I);
> > end;
>
>
> В этом коде _две_ ошибки.

Зависит от архитектуры проекта в целом. Может так оказаться, что и три.

← →
MBo © (2007-04-11 06:43) [96]

Задача: Есть файл 16 гигабайт, содержащий числа Double. Как (эффективно) выбрать из него миллион наибольших чисел, если свободных памяти и дискового пространства только порядка 10 мегабайт?

← →
SlymRO © (2007-04-11 07:51) [97]

MBo © (11.04.07 6:43) [96]
array[миллион] of double - 7,63Мб какие сложности? самое главное этот милион сортированным держать.

← →
MBo © (2007-04-11 08:00) [98]

>SlymRO © (11.04.07 07:51) [97]
Хорошее начало. А дальше как?

← →
SlymRO © (2007-04-11 08:03) [99]

Задачка с ограничением на память...
Как проверить полный диск FAT32 максимального для FAT32 объема на отсутствие рекурсивных и пересекающихся цепочек файлов с ограничением по памяти 600кб (в досе) :)

← →
MBo © (2007-04-11 08:10) [100]

>SlymRO © (11.04.07 08:03) [99]
FAT - это же списочная структура, т.е примерно
файл-> первый кластер
кластер = record
Data: array[512]
Next: кластер
end;

так?

← →
SlymRO © (2007-04-11 08:14) [101]

MBo © (11.04.07 8:00) [98]
1.Читаем double
2. сравниваем с Min(из милиона)// если милион сортирован то с 1 значением
3. если больше то Min(из милиона) выталкиваем из милиона и вставляем новое значение (желательно с сохранением сортированности) (но тут трабла, на flat массиве много фетчей памяти)
4. из траблы п.3 появляется следующая задача: поддержание массива данных с сортированном состоянии при обновлениях с минимальным фетчем памяти

← →
SlymRO © (2007-04-11 08:16) [102]

MBo © (11.04.07 8:10) [100]
итого у тебя множество больших односвязных списков в одном адресном пространстве :) и тебе нужно проверить что разные приски не ссылаются на один и тотже элемент, и что нет зацикливаний элементов

← →
MBo © (2007-04-11 08:18) [103]

>SlymRO © (11.04.07 08:14) [101]
ОК, значит, задача свелась к тому, чтобы эффективно поддерживать сортированную структуру, и быстро удалять из нее.

← →
MBo © (2007-04-11 08:22) [104]

>SlymRO © (11.04.07 08:16) [102]
Ага. А сколько может быть начальных кластеров (файлов) - есть ограничения?
Естественное ограничение MaxInt/размер кластера, т.е. порядка 2^22 файлов для кластера 512 байт, или более сильное?

← →
SlymRO © (2007-04-11 08:24) [105]

MBo © (11.04.07 8:18) [103]
свелась
Как в геометрии доказали теорему сославшись на другую доказанную теорему, Доказательство которой нет необходимости приводить за необходимостью доказать только исходную теорему.

← →
SlymRO © (2007-04-11 08:29) [106]

MBo © (11.04.07 8:22) [104]
http://ru.wikipedia.org/wiki/FAT32

← →
MBo © (2007-04-11 08:30) [107]

>MBo © (11.04.07 08:22) [104]
>Ага. А сколько может быть начальных кластеров (файлов) - есть ограничения?

пардон, это я,пожалуй, зря спросил, к ограничениям задачи это не имеет отношения.

>SlymRO © (11.04.07 08:24) [105]
>Как в геометрии доказали теорему сославшись на другую доказанную теорему,

;) нее... Логика предоставила начальные условия для решения задачи, а далее требуются некоторые знания по структурам данных и алгоритмам

← →
ferr © (2007-04-11 08:46) [108]

ОК. Про рекурсивные цепочки я уже знал (нахождение цикла в однонаправленном списке, давал в пятничнх задачах), а для пересекающихся цепочек диска с количеством кластеров до 2^27 (мин. 68 Гиг, что больше ограничения в досе 2 гиг и в Win32 - 32 Гиг) придумалось обнаружение факта пересечения c затратами 512 Кб

>Последние сектора на уникальность?
Нет, до этого не допер.
Битовый массив использовал.

> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

Я бы использовал TFileStream. По первых - универсальнее (позволяет и на Win9x обрабатывать весьма большие файлы). Во вторых - более переносимо (потоки будут работать не только по Винду). В третьих - файловые потоки очень мало уступают в плане скорости технологии FileMapping, если конечно не читать файл по байтам :) В четвертых - потоки проще использовать для обработки действительно больших файлов (хотя кому то может не влом лишний раз будет сделать MapViewOfFile()). В пятых - файловые потоки более экономно работают с памятью (при неумении правильно работать с FileMapping"ом :)

> Я бы использовал TFileStream. По первых - универсальнее
> (позволяет и на Win9x обрабатывать весьма большие файлы)
> . Во вторых - более переносимо (потоки будут работать не
> только по Винду). В третьих - файловые потоки очень мало
> уступают в плане скорости технологии FileMapping, если конечно
> не читать файл по байтам :) В четвертых - потоки проще использовать
> для обработки действительно больших файлов (хотя кому то
> может не влом лишний раз будет сделать MapViewOfFile()).
> В пятых - файловые потоки более экономно работают с памятью
> (при неумении правильно работать с FileMapping"ом :)

Лишь бы что-то ляпнуть, да? Вот причём здесь компонент инкапсулирующий чтения из файла.. Задача стояла в выборе структуры данных для обработки уже считанных данных..

P.S. щас кто-нибудь придёт и скажет что TFileStream гавно, т.к. java ...

Каждый приводит из той области, где копался сам... Вот и все :(

> MBo © (11.04.07 06:43) [96]
> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

И смысл от таких задач по большому счету?
Если пишется код для embeded контроллеров - да, очевидно будет иметь смысл умение/знание всяких таких штук. Или если дисковые тулзы контора пишет - да, тут тоже критично, видимо.

А мне вот - нафиг такое ни раз не понадобилось. Равно как и сортировки - SQL сервер и так сортирует, а накладные расходы в клиентском коде по манипулированю данными в сравнении с ресурсами и временем, которые жрутся SQL-сервером - да просто пренебрежительно малы! Не говоря уже про, например, отъедаемые ресурсы платформой .NET, например. Это ж какую надо прогу наваять, чтобы это перекрыть? Замучаешься.

Реальная задача из практики - укажи какое нужно железо, чтобы эта прога обслуживала 1000 клиенстких подключений при приемлемом (нравится мне конкретность этого слова) времени отклика. А 100 000?

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

Т.е. умеет ли пользовать google (читай: литературу) для решения новых задач.

Хотя, конечно, собеседование - оно чтобы выявить чего вообще знает и умеет собразить, куда забурялся хоть раз...

> IA (10.04.07 22:06) [91]
> > А вот отсутствие проверки Assigned(List), имхо, не является
> > ошибкой.
>
> Разумеется. А потом ищи где у юзера AV выскочило. Проверка
> аргументов должна быть во всех public & protected методах,
> и в private зачастую.

Замечательно.
Пусть наша супер-пупер функция поимела след. вид:

procedure ClearList(List: TList); var I: Integer; begin if Assigned(List) then begin ... //как-то супер правильно чистим. end; end;

и пусть я вызвал ее следующим образом:

var
SuperPuperList: TList;
...
SuperPuperList := TList.Create();
SuperPuperList.Free();
ClearList(SuperPuperList);

Вопрос: что я выиграю в случае наличия проверки Assigned(List)?

Только не надо говорить, что вызывающий код не верен: раз уж мы взялись проверять аргументы, то логично (на мой взгляд) предположить, что наша мега функция будет однозначно детектировать корректность/не корректность входных параметров. Если же она этого не может - то какой смысл эту проверку добавлять?

ferr © (11.04.07 10:07) [114]
гавно, т.к. java
я ооп изучал по java, фрактал мондельброта в распределенке делал... мне нравится жава...
[113] ржунимагу

KSergey © (11.04.07 10:16) [116]
:)
procedure TThread1.Execute;
begin
Sleep(random(1000));
ClearList(SuperPuperList);
end;

procedure TThread2.Execute;
begin
Sleep(random(1000));
SuperPuperList.Free;
end;

> Лишь бы что-то ляпнуть, да? Вот причём здесь компонент инкапсулирующий
> чтения из файла.. Задача стояла в выборе структуры данных
> для обработки уже считанных данных..

> Задача: Есть файл 16 гигабайт, содержащий числа Double.
> Как (эффективно) выбрать из него миллион наибольших чисел,
> если свободных памяти и дискового пространства только порядка
> 10 мегабайт?

Я-то может и загнался малось, но формум-то по Дельфи, вот я и думаю, как можно было бы данную задачу реализовать на Дельфи...

← →
_Аноним (2007-04-11 10:27) [120]

> IA

> Разумеется. А потом ищи где у юзера AV выскочило. Проверка
> аргументов должна быть во всех public & protected методах,
> и в private зачастую.

не ввовдите людей в заблуждение, кто-то может и поверить.

> Что делать если аргумент пустой, кидать ошибку или молча
> обходить зависит от конкретного случая.

А вот за это увольнять надо. И никакой Кнут не поможет

Тестирование... на знание Найти похожие ветки