Я работаю над алгоритмом сортировки, чтобы показать многопоточное выполнение с именем BITONIC, но способ, которым я нахожу запускать его с многопоточностью, - это создание новых объектов и работа в статическом массиве, но это привело меня к невероятно медленной сортировке,с некоторыми отладками - читай распечатки - я обнаружил, что я создаю оскорбительное количество потоков и, следовательно, большое количество объектов, я думаю, что это делает его настолько медленным, но я не могу по-настоящему исправитьпроблема, поэтому, если вы можете дать мне несколько советов, я буду очень благодарен.
Битоническая сортировка похожа на слияние, истинное понимание алгоритма не является действительно необходимым, только знание о потоках и Java
Здесь у меня есть некоторые атрибуты для отдельных потоков
public static int[] data;
private int start, end, size;
private boolean direction;
private int minimumLength = 1;
private final boolean Ascending = true, Descending = false;
У меня есть 2 конструктора, один для первого экземпляра, которые будут устанавливать значение из внешнего выделенного вектора
public MultiThreadedSorter (int[] originalData)
{
data = originalData;
start = 0;
end = size = data.length;
direction = Ascending;
// minimumLength = data.length / Runtime.getRuntime().availableProcessors();
minimumLength = 2;
}
Еще один для рекурсивных делений с новыми значениями для каждого потока
private MultiThreadedSorter (int lo, int hi, boolean dir)
{
start = lo;
end = hi;
size = hi-lo;
direction = dir;
}
Сортировка только для целей инкапсуляцииse
public void Sort()
throws InterruptedException
{
BitonicSort(start, end, direction);
}
Здесь переопределение запуска
@Override
public void run()
{
try
{
BitonicSort(start, end, direction);
} catch (InterruptedException ex)
{
Logger.getLogger(MultiThreadedSorter.class.getName()).log(Level.SEVERE, null, ex);
}
}
Здесь я думаю, что проблема в
private void BitonicSort(int _lo, int _hi, boolean dir)
throws InterruptedException // join()
{
int length = _hi - _lo;
// System.out.println(Thread.currentThread().getName() + " - CRIADA");
// System.out.printf("%d\t%d\n", _lo, _hi);
if (length > 1)
{
// Show ("SORT", true);
if (length > minimumLength)
{
int mid = length / 2;
System.out.println("-- left - " + Thread.currentThread().getName());
MultiThreadedSorter leftSorterObj = new MultiThreadedSorter(_lo, _lo+mid, Ascending);
Thread left = new Thread(leftSorterObj);
left.start(); // i think that the problem is here
left.join(); // or here
System.out.println("-- rigth - " + Thread.currentThread().getName());
// System.out.printf("%d\t%d\n", _lo+mid, _hi);
MultiThreadedSorter rightSorterObj = new MultiThreadedSorter(_lo+mid, _hi, Descending);
Thread right = new Thread(rightSorterObj);
right.start(); // i think that the problem is here
right.join(); // or here
// System.out.println(Thread.currentThread().getName() + " - ENDED\n");
}
else
{
int mid = (length / 2);
if (mid > 1)
{
// Show ("R1", false);
BitonicSort(_lo, mid, Ascending);
// Show ("R2", false);
BitonicSort(_lo+mid, mid, Ascending);
}
}
BitonicMerge(_lo, _hi, dir);
}
}
А теперь я выложу основной иполный класс, только если вы хотите выполнить
MAIN:
public class Program
{
public static void main(String[] args) throws InterruptedException
{
Random random = new Random();
int arraySize = (int) Math.pow(2, 7);
int[] originalData = new int[arraySize];
int lim = 20;
for (int i = 0; i < originalData.length; i++)
originalData[i] = random.nextInt(lim);
System.out.println(Arrays.toString(originalData));
System.out.printf("\n");
MultiThreadedSorter mult = new MultiThreadedSorter(originalData);
mult.Sort();
System.out.println(Arrays.toString(originalData));
System.out.println();
}
MultiThreadedSorter CLASS
public class MultiThreadedSorter //extends BaseBitonicSorter
implements Runnable
{
public static int[] data;
private int start, end, size;
private boolean direction;
private int minimumLength = 1;
private final boolean Ascending = true, Descending = false;
public MultiThreadedSorter (int[] originalData)
{
data = originalData;
start = 0;
end = size = data.length;
direction = Ascending;
// minimumLength = data.length / Runtime.getRuntime().availableProcessors();
minimumLength = 2;
}
// Construtor chamados por cada thread antes de iniciar
private MultiThreadedSorter (int lo, int hi, boolean dir)
{
start = lo;
end = hi;
size = hi-lo;
direction = dir;
}
public void Show (String msg, boolean r)
{
System.out.println(Thread.currentThread().getName() + "\t" + msg);
if (r)
System.out.printf("De: %d\tAte: %d\t Dir: %d\n", start, end, direction ? 1 : 0);
}
@Override
public void run()
{
try
{
BitonicSort(start, end, direction);
} catch (InterruptedException ex)
{
Logger.getLogger(MultiThreadedSorter.class.getName()).log(Level.SEVERE, null, ex);
}
}
public void Sort()
throws InterruptedException
{
BitonicSort(start, end, direction);
}
private void BitonicSort(int _lo, int _hi, boolean dir)
throws InterruptedException // join()
{
int length = _hi - _lo;
// System.out.println(Thread.currentThread().getName() + " - CRIADA");
// System.out.printf("%d\t%d\n", _lo, _hi);
if (length > 1)
{
// Show ("SORT", true);
if (length > minimumLength)
{
int mid = length / 2;
System.out.println("-- left - " + Thread.currentThread().getName());
MultiThreadedSorter leftSorterObj = new MultiThreadedSorter(_lo, _lo+mid, Ascending);
Thread left = new Thread(leftSorterObj);
left.start();
left.join();
System.out.println("-- rigth - " + Thread.currentThread().getName());
// System.out.printf("%d\t%d\n", _lo+mid, _hi);
MultiThreadedSorter rightSorterObj = new MultiThreadedSorter(_lo+mid, _hi, Descending);
Thread right = new Thread(rightSorterObj);
right.start();
right.join();
// System.out.println(Thread.currentThread().getName() + " - ENDED\n");
}
else
{
int mid = (length / 2);
if (mid > 1)
{
// Show ("R1", false);
BitonicSort(_lo, mid, Ascending);
// Show ("R2", false);
BitonicSort(_lo+mid, mid, Ascending);
}
}
BitonicMerge(_lo, _hi, dir);
}
}
private void BitonicMerge(int _lo, int _hi, boolean dir)
throws InterruptedException // join()
{
// Show ("MERGE", true);
int length = _hi - _lo;
if (length > 1)
{
if (length > minimumLength)
{
int mid = (length / 2);
for (int i = _lo; i < (_lo + mid); i++)
Compare(i, (i + mid), dir);
MultiThreadedSorter leftMergerObj = new MultiThreadedSorter(_lo, _lo+mid, dir);
Thread left = new Thread(leftMergerObj);
left.start();
left.join();
MultiThreadedSorter rightMergerObj = new MultiThreadedSorter(_lo + mid, _hi, dir);
Thread right = new Thread(rightMergerObj);
right.start();
right.join();
}
else
{
int mid = (length / 2);
for (int i = _lo; i < (_lo + mid); i++)
Compare(i, (i + mid), dir);
if (mid > 1)
{
BitonicMerge(_lo, _lo + mid, dir);
BitonicMerge(_lo + mid, _hi, dir);
}
}
}
}
private synchronized void Compare(int src, int dst, boolean dir)
{
if (dir == (data[src] > data[dst]))
Exchange(src, dst);
}
protected synchronized void Exchange(int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}