Comments 16
Если ничего не сказано про размер входного файла, то оценка в 30 сек - ни о чём.
Что-то как-то всё сложно. Я так и не понял что за вершины у вас в графе, но кажется что вы просто используете значения в качестве вершин. Это совершенно неправильно, вот на таких исходных данных у вас будет ошибка:
1;2;3
4;5;1Здесь у строк нет совпадений ни в одной колонке, но вы ведь всё равно их отнесёте в одну группу?
Для нормального решения задачи надо не списки выбирать (хотя чего их выбирать, ArrayList всегда лучше если вам достаточно интерфейса List), а построить нормальный граф, который отражает исходную задачу.
Я бы строил его как двудольный, левая доля — строки, правая доля — пары из номера колонки и значения в ней. Никаких groupMap и groupList тут быть не должно.
PS в вашем коде невозможно разбираться. Вас что, штрафуют за созданные классы? Как вы вообще помните какой из List в вашем List<List<List<String>>> за что отвечает?
Вот так же гораздо понятнее:
class Row {
public List<String> Values = new ArrayList<>;
}
class RowGroup {
public List<Row> Rows = new ArrayList<>();
}
private Graph<String, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);
private Map<String, RowGroup> groupMap = new HashMap<>();
private List<RowGroup> groupList = new LinkedList<>();Или вот, для моего варианта графа:
sealed interface Vertex {}
class Row implements Vertex {
public List<String> Values = new ArrayList<>();
}
record RowValue(int column, String value) implements Vertex {}
private Graph<Vertex, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);
Навскидку, тут прям напрашивается DSU
Согласен с мнением @mayorovp, что вершинами должны быть строки. Плюс понадобится хэшмэп ((колонка+значение) -> вершина), ну или отдельный хэшмэп (значение -> вершина) для каждой колонки. Для очередной строки проходим по всем её значениям, и если нашли смежную вершину по хэшмэпу, то присоединяем к её группе. Это позволит быстро обрабатывать кейсы, когда строка соединяет две большие группы (собственно, для чего DSU и придумана).
Это точно код для современной java? Напишу несколько замечаний, чтобы новички знали как делать не надо.
Открыли I/O stream / reader – не забудьте его закрыть, try with resources в этом поможет.
Для работы с локальными файлами есть Files, для работы с classpath ресурсами в экосистеме spring – Resource.
Ручная итерация через iterator моветон уже лет 20 как, если не больше.
Нет инкапсуляции, поля должны быть скрыты, доступ через getter-ы.
Дикая сложность алгоритма, цикл циклом погоняет (стримы внутри циклов). Стоило вычитать все строки, построить таблицу соответствия, а уже потом устанавливать связи для графа.
Чисто для визуальной чистоты в современной java для ссылок можно указывать var.
В подавляющем большинстве случаев ArrayList наше все.
Как уже упоминули выше, что это за 30 сек и для какого объема данные? Как проводили замеры? Для создания бенчмарков используем JMH.
В постах про выбор реализации списка невозможно удержаться от цитаты:
Так замеры не делаются. Нужно срочно все перевести на JMH (https://github.com/openjdk/jmh) с прогревом JVM и прогоном в минимум 10 раз с выведением средних результатов. Нельзя утверждать о каких-то сравнениях, не предоставив информацию о входных данных (размер входного файла, характеристики железа, сборка и версия JDK и так далее).
Ну и в дополнение к цитате Joshua Bloch, Шипилёв говорил, что знает только пару кейсов, когда можно использовать LinkedList вместо ArrayList, но даже тогда выигрыш настолько несущественный, что проще всегда использовать ArrayList ;)
Плоскогубцы vs. Кусачки
Друзья, на столь простой задаче мы побили все рейтинги..) Статья, конечно, носит обзорный характер. Тема "LinkedList & ArrayList" не подлежит какому-то серьезному обсуждению.. Тем не менее, приятно, что (не сильно подготовленная к публикации) заметка, вызвала столько комментариев. Основной интерес, полагаю, вызван применением, рассмотренном на простом примере, библиотеки jgrapht.
grigorym - размер входного файла - в репозитории.
mayorovp - у приведенных строк есть совпадения, в первой и последней колонках.
tmk826 - полностью согласен) "Плоскогубцы vs. Кусачки" Метрики и научный подход здесь, пожалуй, будет лишними. Joshua Bloch, Шипилёв... ) Да, знаем. Авторы не безизвестные
vasyakolobok77 ..бэнчмарки для этой задачи, нет, правда - я пас.
Alexandroppolus ..а вот это - полезный комментарий, по сути задачи. Спасибо. Принято к сведению
у приведенных строк есть совпадения, в первой и последней колонках
Термин "совпадение в колонке" означает что у двух строк есть одно значение в одной и той же колонке. "Совпадение в одной и более колонках" — это применение квантора существования по переменной "колонка" к "совпадению в колонке".
@mayorovp успел обидеться, а зря. Все проще, без кванторов. Совпадения <по колонке> (не допускается иного понимания):
1;2;3
1;5;01;2;3
4;5;1"Здесь у строк нет совпадений ни в одной колонке, но вы ведь всё равно их отнесёте в одну группу? "
Для особо одаренных, есть пример в условии задачи (текст взят из задачи к тех. собеседованию одной из организаций):
если строчки имеют совпадения непустых значений в одной или более колонках,
они принадлежат одной группе. Например, строчки:
111;123;222
200;123;100
300;;100все принадлежат одной группе, так как первые две - имеют одинаковое значение 123 во второй колонке, а две последние одинаковое значение 100 в третьей колонке.
Не забываем поставить like) = "-1" ) и выложить хоть одну публикацию с кодом на git-е. "Возвращение работоспособности переключения раскладки через правый Alt + Shift ..", это слишком сурово
Этот пример моему толкованию условий задачи не противоречит, потому что в нём как раз все совпадения строго в пределах колонки: 1 и 2 строки совпадают по второй колонке, 2 и 3 строки совпадают по третьей колонке.
Что же до публикаций с кодом на гите — что-то я не видел подобного требования в правилах Хабра.
Еще раз… вопрос выбора: LinkedList & ArrayList