Здравствуйте, -n1l-, Вы писали:
ST>>Совет, видимо, должен был быть таким:
ST>>"Напиши сортировку пузырьком многопоточную и сравни ее с однопоточной с точки зрения эффективности и сложности".
N>Однопоточная сортировка пузырьком проще пишется, но медленнее выполняется. У меня нет в коде разделения задачи на потоки, я как бы разделил вычисления и пользовательский интерфейс, так что у меня асинхронное выполнение программы.
Звучит очень опрометчиво. Есть задачи, которые очень плохо параллелятся и пузырьковая сортировка — это один из таких примеров. На самом деле, не редки случаи, когда параллельное решение будет *медленнее* простого последовательного, поэтому чтобы сказать, что-то работает быстрее, то для начала: (1) это что-то должно работать правильно и (2)эффективность должна быть доказана.
Не стоит забывать о
законе Амдала, что "когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента".
ST>>(И еще, а насколько пузырьковая сортировка параллелится? Мне кажется, что это сверх сложная задача для параллелизма;
N>Я, пока что, еще не знаю что конкретно от меня хотят видеть в качестве многопоточной сортировки пузырьком. Но исходя из сообщений выше, думаю это будет архисложно и жутко запутанно.
От тебя никто ничего не хочет
Это был небольшой вброс. Я бы посоветовал погуглить на тему
"embarrassingly parallel" задач (т.е. задач, "чрезвычайно подходящих для параллелизма"), которые следует попробовать решить. Именно поэтому я посоветовал взять другие алгоритмы сортировки, более подходящими для параллелизма.
ST>>При этом ты добавил кучу проблем, не решив ни одной исходной. Главной бедой (ладно, одной из главных) многопоточности и параллелизма является гонки или борьба за разделяемые ресурсы, которая у тебя проявляется во всей красе!
N>Да, уверен, что вывод результата попросту выполнился перед сортировкой.
N>Быстронаписанный код, что бы привлечь в тему больше людей.
Это привлечет одних людей, но отпугнет других
ST>>Я бы, подходя к этому решению постарался бы сразу сделать вменяемый API сортирвки (глянув на тот же LINQ-овский OrderBy), а затем сравнил бы эффективность своего решения со "стандартным" — с PLINQ-овским OrderBy.
N>Что вы понимаете под "api сортировки"? Метод расширения с linq подобным синтаксисом. Быть может. Первое, что я делаю, это решение в лоб.
Я понимаю то, что ни одно из существующих решение не модифицирует исходный массив (коллекцию), а возвращает новую. Это сделает проверку более простой задачей и избавит от целого класса проблем за счет устранения разделяемых ресурсов.
Здравствуйте, SergeyT., Вы писали:
ST>Звучит очень опрометчиво. Есть задачи, которые очень плохо параллелятся и пузырьковая сортировка — это один из таких примеров. На самом деле, не редки случаи, когда параллельное решение будет *медленнее* простого последовательного, поэтому чтобы сказать, что-то работает быстрее, то для начала: (1) это что-то должно работать правильно и (2)эффективность должна быть доказана.
ST>Не стоит забывать о законе Амдала, что "когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента".
Хорошо, пузырьковая сортировка — это сортировка, котрую лучше не распараллеливать.
ST>Я понимаю то, что ни одно из существующих решение не модифицирует исходный массив (коллекцию), а возвращает новую. Это сделает проверку более простой задачей и избавит от целого класса проблем за счет устранения разделяемых ресурсов.
Ясно.
Да, кстати, если уж вопрос зашел за книги, не могли бы вы мне подсказать русскоязычные названия книг приведенных ниже.
раз
два
Ссылки не сработали.
1)Synchronization Algorithms and Concurrent Programming
2)Principles of Concurrent and Distributed Programming
По дословному, так сказать, переводу найти не смог.