Определить что элементы одной коллекции являются квадратными корнями другой?

Question

[Василий]

Подскажите можно-ли написать более оптимальный алгоритм. Задача звучит так:

Нужно проверить что все в коллекции squares являются квадратными корнями чисел в коллекции numbers. Коллекции отсортированы по возрастанию и не имеют отрицательных значений.

update: если коллекции разной длины то считаем это как false

Примеры входных данных и ответы:
IN: {1, 2}, {1, 4} OUT: TRUE

IN: {1, 3, 5}, {1, 9, 25, 25} OUT: FALSE

Сигнатура функции:

bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares)

Моё решение:

public static bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares) {
    var isFirstIteration = true;
    var numbersEnumerator = numbers.GetEnumerator();
    var squaresEnumerator = squares.GetEnumerator();

    while (true) {
        bool numberHasNext = numbersEnumerator.MoveNext();
        bool squareHasNext = squaresEnumerator.MoveNext();

        if(numberHasNext != squareHasNext) {
            // случай когда две коллекции имеют разный размер

            return false;
        }

        if(!numberHasNext && !squareHasNext) {

            if (isFirstIteration) {
                // случай когда две коллекции пусты
                return false;
            }

            break;
        }

        var testData = numbersEnumerator.Current * numbersEnumerator.Current;
        if(testData != squaresEnumerator.Current) {
            return false;
        }

        isFirstIteration = false;
    }

    return true;
}

p.s.

Так же интересует решение с той же оптимальностью но не такое многословное.

Comments

[Сергей Соколов]

не программирую на C, поэтому может глупый вопрос: обе коллекции точно отсортированы так что current'у числа соответствует именно его квадрат?

[Василий]

Сергей Соколов, да согласно заданию мы предполагаем что обе коллекции отсортированы, и это не си а сишарп

[Василий]

Лентюй, поясните пожалуйста почему будет врать даже на коллекциях одинаковой длины? В чем ошибка?

[Василий]

Лентюй, да потому что второй элемент из в второй коллекции != 1*1, и это правильно, для numbers = {1,1,1} правильно будет squares = {1,1,1}

[Василий]

Лентюй, прошу прощения я некорректно написал задание

[Lynn «Кофеман»]

А почему для пустых коллекций ответ false?

[Василий]

Алексей Тен, полагаю что наверное потому что в пустой коллекции нет никаких корней

[Lynn «Кофеман»]

По теме, если использовать foreach, то можно сократить наполовину.
Псевдокод

s = squares.getEnumerator();
foreach(int number in numbers) {
  if (!sq.MoveNext()) { return false; } // второй список короче
  if (number * number !== sq.Current) { return false; }
}
if (sq.MoveNext()) { return false; } // второй список длиннее
return true;

[Василий]

Алексей Тен, это похоже на то что я искал, сделайте ответом пожалуйста

[#]

Василий, почему IEnumerable?
есть нюансы, сильно влияющие на решение

[Василий]

#, ну я предполагаю что мы не знаем этого и делаем библиотечную функцию оптимальную и для массивов и для потоков

[#]

Василий,

библиотечную функцию оптимальную и для массивов и для потоков

пустое. по требованию вернуть bool вы уже обязаны перебрать по меньшей мере один из источников полностью

ps как только вы сделали хоть одну выборку из источника IEnumerable, если источник хоть где либо еще используется в коде, то наличие неявной полной копии гарантировано

функция с такой спекой нивелирует все попытки увернуться от .ToList<>()
однако кодирование вы себе уже усложнили. ментра

вариант аллоцирует лишнюю память, и делает лишние вычисления

приводит вас к потере времени на разработку

Answer 1

[Lynn «Кофеман»]

Disclaimer: Я не пишу на C# так что возможны ошибки, но идея простая, надо использовать foreach.
Эта функция вернёт true если обе коллекции пусты.

public static bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares) {
    var squaresEnumerator = squares.GetEnumerator();

    foreach(int number in numbers) {
        if(!squaresEnumerator.MoveNext()) {
            // в squares закончились элементы, а в numbers ещё нет
            return false;
        }

        if(number * number != squaresEnumerator.Current) {
            return false;
        }
    }

    if(squaresEnumerator.MoveNext()) {
        // в squares ещё остались элементы, а в numbers уже всё закончилось
        return false;
    }

    return true;
}

Comments

[#]

небольшая оптимизация

public static bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares)
        {
            var fail = false;
            var sq = squares.GetEnumerator();

            foreach (var n in numbers)
                if (fail = !(sq.MoveNext() && (n * n == sq.Current)))
                    break;

            return !(fail || sq.MoveNext());
        }

[#]

вычисления логических выражений в C# ленивые по дефолту

[Lynn «Кофеман»]

Ну да.
Но у меня рука не поднимается писать присваивания в условиях

[#]

Алексей Тен, это только вопрос читаемости, если все компактно и логично - в чем трудности?
в любых языках си-синтаксиса, в тч и в js это нормально

при этом код в несколько строк, всегда воспринимается легче кода в несколько десятков строк

Answer 2

[Griboks]

Если речь про оптимальную длину кода, то можно использовать что-то в этом роде:

bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares) =>  numbers.Count == squares.Count && squares.Select(x=>x*x).All(x=>numbers.Contains(x));

C учётом правок задания и комментариев.

Comments

[freeExec]

Не пройдёт, когда в squres есть лишнее число.
Надо наоборот

squares.Select(x=>x*x).All(x=>numbers.Contains(x));

[Василий]

Прошу прощения, я исправил постановку задачи, была неточность.

[Griboks]

Василий, тогда

bool TestForSquares(IEnumerable<int> numbers, IEnumerable<int> squares) =>  numbers.Count == squares.Count && numbers.Select(x=>x*x).All(x=>squares.Contains(x));

freeExec, наоборот вы проверяете, что squares - это квадратные корни numbers. Количество элементов в коллекциях ни на что не влияет (до редактирования вопроса).

[Griboks]

Василий,

вариант аллоцирует лишнюю память, и делает лишние вычисления, если у вас в первом же элементе нет совпадений, то остальные вычисления не имеют смысла

Тогда опять редактируйте вопрос. Сейчас задача на множества, а не на пары numbers[i]==sqrt(squares[i]). Linq сам по себе выделяет много чего лишнего и медленно работает. Мой вариант оптимален только по количеству нажатий клавиатуры.

[freeExec]

Griboks,
1) squares - это корень, а не квадрат, вы не то проверяете. Если numbers = 4, то squares должен быть 2, а не 16 как вы проверяете.
2) но даже если предположить другую зависимость у вас даст не тот результат при n = {1, 2, 2} s={1, 4, 8} т.к. для восьмёрки нет значения в numbers. А условие звучит как все в коллекции squares являются квадратными корнями

[Griboks]

freeExec, Василий,

squares - это корень, а не квадрат, вы не то проверяете.

квадратный корень - это square root, но вы правы по условию. Их надо поменять местами. Исправил ответ.

не тот результат при n = {1, 2, 2} s={1, 4, 8}

Выдаст true. Давайте проверим: 1*1=1 присутствует в s, 2*2=4 присутствует в s, 2*2=4 присутствует в s. Всё правильно.

[freeExec]

Griboks,

Выдаст true.

А не должен, ведь для 8 нет значения в n

[Griboks]

freeExec, так надо проверить, что элементы являются квадратными корнями, а не что элементы являются квадратами.

Answer 3

[freeExec]

Задача на работу со множествами.

static bool TestSet(IEnumerable<int> numbers, IEnumerable<int> squares)
{
    var ns = new HashSet<int>(numbers.Select(n => (int)Math.Round(Math.Sqrt(n))));
    return ns.IsSupersetOf(squares);
}

Comments

[Василий]

Ваш вариант аллоцирует лишнюю память, и делает лишние вычисления, если у вас в первом же элементе нет совпадений, то остальные вычисления не имеют смысла

[Василий]

Прошу прощения, я исправил постановку задачи, была неточность.