Предыдущий пост Поделиться Следующий пост
Поиск фигни
lex_kravetski
Кстати, придумал задачу для любителей запаха монад по утрам, да и вообще для заинтересованных.

Есть у нас данные на сетке. Для простоты они сложены в двумерный массив. Данные намерянны каким-то прибором, который мог сломаться, что мы, в частности, узнаём по наличию в любой точке сетки значения, превышающего заранее заданную величину maxValue. Нам надо выяснить, не сломался ли прибор как минимум по этому критерию, но не просто выяснить, а ещё показать любое значение, превысившее максимальное — чисто для пафоса. У вас-де вот в этой точке аж вот столько, чините прибор.

Решение задачи с императивным подходом просто и прозаично.

int value = 0; 
a: for (int x = 0; x < xSize; x++) {
    for (int y = 0; y < ySize; y++) {
        int v = data[x][y];
        if (v > maxValue) {
            value = v;
            break a;
        }
    }
}


Прозаично, понятно и правильно работает, но не круто. Круто написать то же самое не просто на Scala, но с for-comprehension или с использованием каких-то методов scala-коллекций и без break. При этом написать так, чтобы оно было короче и не имело существенных просадок по производительности в сравнении с данным конкретным примером.

Дерзайте, друзья.

  • 1
(Удалённый комментарий)
Я, увы, плохо знаю Haskell. Поэтому не могу прокомментировать.

(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
data.flatten.find(_ > maxValue).

Так нормально?

С find — это чит. Но, кстати, всё равно условие не выполнено: имеет место быть суровая просадка по производительности.

Ну вы сначала задачу более полно сформулируйте:

а) Исходный код на каком языке? Если на Си - то break не разорвет наружный цикл!
б) Требуется ли найти индексы?
в) у вас ySize < ySize вместо y < ySize;
г) прозаичный код не работает, если есть отрицательные элементы как что вы собираетесь с полученным значением потом делать? возвращать из функции?
д) Можно ли использовать список списков или массив массивов?

Edited at 2012-08-30 11:39 (UTC)

приведённый обход не будет работать, если максимально допустимое значение отрицательное.

Исходны код на чём?
Если на С, то точнее будет так:

int value = data[0][0];
int x, y;
for (x= 0; value < maxValue; x++)
{
for (y = 0; value < maxValue; y++)
{
value = data[x][y];
if (x == xSize) break;
}
if ( y == ySize) break;
}

Вообще что значит "круто".
Коротко ради краткости или есть ещё какие-то достоинства?

П.С.
да, отступы в отображении *html поехали ((

int value вообще нафик не нужна.
Да тем более - с инициализацией.

Re: Ответ на вашу запись "Поиск фигни"

Я её сделал, чтобы показать, что именно мы получаем.

На додиезе.

            var data = new int[][] { };
            var res = (from x in data.AsEnumerable()
                      from y in x
                      where y > 100
                      select y).FirstOrDefault();


Лениво разворачивать в прямой вызов функций, но будет как-то так


var res2 = data.AsEnumerable().Select(x => x.SelectMany(y => y).Where(value => value > 5)).FirstOrDefault();



И оно работает благодаря тому, что внутре у ней неонка. То есть прописан джойн. и монадыЪ

Пруф http://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads

И по чистой случайности люди, которые отвечали за реализацию Linq в C# входят в группу разработки Haskell.



Не слабо так входят, учитывая что Simon Peyton Jones последние 14 лет работает в Microsoft Research

c#
data.SelectMany(x => x).FirstOrDefault(v => v > maxValue);

(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)

Просто и прозаично?

С момента публикации задачи вы исправили как минимум две фатальных ошибки в программе на 7 строчек.

Метка для break и y < ySize. Может быть я пропустил что-то ещё.

Что, простите, простого оказалось в вашей реализации?

size_t i = size_x * size_y; while (--i >= 0) {
	int v = *((int *)(a) + i);
	if (v > max) {
		return v;
	}
}
извините, что не на скале.

Чуть идиоматичней, и не хуже по перформансу:
for(size_t i = 0; i < size_x * size_y; i++) {
    if(a[0][i] > max) return v;
}

Предположим

Что двумерный массив реализуется одномерным вектором. Это удобно, при желании можно написать короткий класс, который будет пересчитывать i,j в смещение.

vector matrix(NM);
...
sort(matrix.begin(),matrix(end));
if(*(matrix.end()-1) > maxValue) )
return (*(matrix.end()-1);
else return defaultValue;

Сложность логарифмическая, а не квадратичная.

Re: Предположим

В оригинальном задании сложность O(N) от количества элементов, у тебя O(N*logN).

select /*+ INDEX d (ind_x,ind_y) */ greatest(d.x,d.y) from data d where (d.x > :maxValue or d.y > :maxValue) and d.rownum = 1


Правда ли что ,
все программы которые пишет Лекс - политические ?
:)


Свежее решение!!!

В качестве шутки, прочитал все комментарии, ужаснулся, сколько интеллектуальных усилий потрачено.
Предлагаю алгоритм контроля прибора встраивать в алгоритм считывания данных с прибора (там ему, по уму, и место), тогда он будет божественно красив и займет одну строчку "если то".

вариант на OCaml, ЯП вроде бы семантически и идеологически близком к Scala. думаю, идею тут легко уловить. Сдаётся мне по-функциональному, то бишь без break, вряд ли проще получится. Впрочем, и то не то чтобы сложный для понимания код

let find_fignja (data: int [] [] ) maxValue =  
    let rec loopn n =  
        if n>=data.Length then None else
        let rec loopi i =  
            if i>=data.[n].Length then None else
            if data.[n].[i]>=maxValue then Some data.[n].[i] else loopi (i+1) 
        match loopi 0 with
        | None -> loopn (n+1) 
        | x -> x 
    loopn 0

  • 1
?

Log in

No account? Create an account