Олег Кириченко @infosave
Программист
Информация
- В рейтинге
- Не участвует
- Откуда
- Турция
- Дата рождения
- Зарегистрирован
- Активность
Специализация
Application Developer, Web Developer
Lead
PHP
MySQL
Database
Software development
Database design
Code Optimization
Multiple thread
Git
Golang
SQL
На самом деле тема не такая очевидная как Вам кажется, думаю многим пригодиться, не все такие задачи решают за 2 секунды (мне потребовалось 3 дня чтобы найти способ), все пока работает без блокировок от Телеграмм, пока не является нарушением. У нас сейчас 28 пользователей платформы типа https://nk.coursefactory.pro/ пока проект развивается, в каждом кабинете уже добавлено прилично групп и каналов.
Если пользователь находится в других группах то фиксируется только тот под чей ID он импортировался первым, если нет юзернейма то естественно не импортируется и не пойдет по партнерской программе.
Не спамить сейчас не модно, попробую объяснить идею проще, например у Вас есть Телеграм канал/группа на 50000 человек, я Вам предлагаю провести на Вашем канале стрим с продвиженим моих курсов актерского мастерства, Вы регистрируетесь на моем сайте для получения партнерского вознаграждения и даете мне права для того чтобы я смог спарсить все логины под Ваш ID, потом я провожу тестовые занятия на Вашем канале и предлагаю купить мои курсы. Допустим регистрируеся на мой сайт пользователь @xxxxxxx и он пришел получается с Вашего канала, тогда при покупке курса за 80000 рублей, Вам начисляют 6000 рублей по партнерской программе, а если пользователь @xxxxxxx пригласил друзей то Вы еще получите вознаграждение и от его друзей и друзей друзей (в нашем проекте партнерка 3 уровня)
Наглядность для разработчика, виден полный путь, можно сильно поспорить насчет времени запроса, надо сравнить и выбрать лучший вариант, сейчас пишу 2 часть статьи с тестами моего алгоритма нахождения минимального пути в графе с помощью матрицы 5xN по сравнению оптимизированным алгоритмом Дейкстры
Мой метод предоставляет интуитивную наглядность и гибкость для работы с произвольным количеством дочерних элементов, что упрощает внедрение и сотрудничество в команде. Он также позволяет выполнять специфические выборки одним запросом, как и Nested Sets, но с меньшей сложностью и более простым пониманием структуры данных, что может быть преимуществом в MLM-структурах.
Сделаю статью часть 2 где выложу примеры и графики, на Github выложил коды оптимизированного Дейкстры и пример теста (benc.php), так же Вы можете посмотреть рабочий код https://phpize.online/s/YC
Я просил ссылку на алгоритм или готовый код для того чтобы сравнить алгоритмы на производительность, а так же код размещу на Github с настройками и генератором случайных графов для заполнения матриц.
Алгоритм Флойда-Уоршелла находит кратчайшие пути между всеми парами вершин во взвешенном графе, имеет временную сложность O(|V|^3) и работает с отрицательными весами рёбер (но не с отрицательными циклами). Алгоритм 5xN находит кратчайший путь между двумя вершинами, имеет временную сложность O(|V| * |E|) и не учитывает отрицательные веса рёбер и циклы. Выбор алгоритма зависит от задачи и структуры графа.
Да Вы правы для графе с 5 рёбрами и 5 вершинами алгоритм Дейкстры действительно будет выполнять гораздо меньше операций, чем я указал ранее. Ваш расчет операций (5 * (log(5) + log(5))) корректно отражает количество базовых сравнений для такого случая, что составляет около 30. Выше я написал, что проведу тестирование, могли бы Вы написать ссылку на алгоритм Дейкстры который максимально оптимизирован или есть готовая быстрая библиотека на php или golang?
Я искренне рад, что моя статья привлекла столько внимания и вызвала интерес у читателей. Обязательно выделю время на проведение бенчмарков с разными вариантами алгоритма, чтобы сравнить его производительность с алгоритмом Дейкстры и другими алгоритмами поиска кратчайшего пути. Возможно, в процессе тестирования я смогу определить потенциал для дальнейшей оптимизации алгоритма 5xN, что позволит его использование стать еще более эффективным в различных сценариях. Благодарю за предложение и за активное участие в обсуждении.
Пример кода лежит на Git в папке с примерами get_users_by_level.php
Ваш вариант будет выглядеть
все варианты решения я не предусмотрю
Спасибо за интерес к этому алгоритму, я еще раз все проверю и обновлю на git если найдутся ошибки
Алгоритм Дейкстры имеет временную сложность O(|V|^2) для наивной реализации или O(|V| * log|V| + |E| * log|V|) с использованием приоритетной очереди. В нашем случае, это будет примерно равно O(10 000^2) = 100 000 000 или O(10 000 * log10 000 + 50 000 * log10 000) ≈ 1 653 963 для оптимизированной реализации.
Алгоритм 5xN, в свою очередь, может иметь временную сложность O(|V| * |E|), что составляет примерно O(10 000 * 5) = 50 000.
Как видно из этого примера, алгоритм 5xN может быть более эффективным с точки зрения времени выполнения, особенно при определенных условиях, например, когда количество ребер в графе ограничено. Однако стоит заметить, что эффективность алгоритма 5xN может сильно зависеть от его реализации и конкретной задачи. С помощью этого алгоритма решались реальные задачи, ошибок небыло.
Да для полных графов алгоритм не эффективен, для разреженных выбор процессор или память, если много памяти то можно и алгоритм Дейкстры
Спасибо за Ваши уточнения, попробую внести корректировки в Git, Вы хотите готовое решение для Вашей задачи?
Прочтите пожалуйста пункт недостатки алгоритма, для большого списка задач этот алгоритм использовать эффективнее
Согласен что материализованный путь был открыт очень давно и описывался в учебниках наверное по первым FoxPro базам данным в 90 годах, я предоставил пример реализации с некоторыми нюансами которые позволяют снизить нагрузку на SQL сервер, поэтому в таблице хранится уровень и количество приглашенных (при больших объемах базы значительные нагрузки). Выбрал тематику MLM потому, что проблема возникла в этой сфере, притом в компании занимающейся косметикой, а не очередной пирамидой.