ستوضح هذه المشاركة كيفية تنفيذ الفرز في جافا باستخدام ExecutorService. جوهر الفرز العام كما يلي:- يتم تقسيم الصفيف إلى أجزاء
- يتم فرز كل جزء من المصفوفة.
- نذهب من خلال المصفوفات المطلوبة ، ودمجها في واحدة
هنا يتم تطبيق أفكار دمج الفرز ، ولكن يتم تقسيم الصفيف فقط إلى جزأين (لا يتم استخدام العودية).يمكنك استخدام الوظيفة التالية للدمج:public static String[] merge( String[] leftPart, String[] rightPart ) {
int cursorLeft = 0, cursorRight = 0, counter = 0;
String[] merged = new String[leftPart.length + rightPart.length];
while ( cursorLeft < leftPart.length && cursorRight < rightPart.length ) {
if (leftPart[cursorLeft].compareTo(rightPart[cursorRight] ) < 0 ) {
merged[counter] = leftPart[cursorLeft];
cursorLeft+=1;
} else {
merged[counter] = rightPart[cursorRight];
cursorRight+=1;
}
counter++;
}
if ( cursorLeft < leftPart.length ) {
System.arraycopy( leftPart, cursorLeft, merged, counter, merged.length - counter );
}
if ( cursorRight < rightPart.length ) {
System.arraycopy( rightPart, cursorRight, merged, counter, merged.length - counter );
}
return merged;
}
كود وظيفة الدمج مأخوذ من هنا .جوهر الدمج هو هذا: في البداية ، تكون المؤشرات على العنصر الأول لكل من المصفوفتين. بعد ذلك ، تتم مقارنة قيم العناصر المقابلة لمواضع المؤشر ويتم تحويل مؤشر العنصر الأصغر إلى العنصر التالي ، ويتم إضافة العنصر نفسه إلى الصفيف الناتج. تستمر الدورة حتى نصل إلى نهاية أحد المصفوفات ، ثم يتم نسخ باقي المصفوفة الثانية إلى نهاية المصفوفة الناتجة. وبالتالي ، فإن الإخراج عبارة عن صفيف مفروز.تم أيضًا إنشاء فئة للفرز متعدد مؤشرات الترابط ؛ تم إنشاء طريقة تشغيل فيه ، والتي يتم تنفيذها عند تطبيق طريقة start () على كائن من نوع Thread. في حالتنا ، ستكون خدمة المنفذ التنفيذية مسؤولة عن ذلك. إليك كود فئة الدمج ، التي سيتم إنشاء كائناتها لتنفيذ الفرز متعدد مؤشرات الترابط:
public class Merger implements Runnable{
private String[] unsorted, sorted;
public Merger(String[] unsorted) {
this.unsorted = unsorted;
}
public void run() {
int middle;
String[] left, right;
if ( unsorted.length <= 1 ) {
sorted = unsorted;
} else {
middle = unsorted.length / 2;
left = new String[middle];
right = new String[unsorted.length - middle];
System.arraycopy(unsorted, 0, left, 0, middle);
System.arraycopy(unsorted, middle, right, 0, unsorted.length - middle);
SimpleMerger leftSort = new SimpleMerger(left);
SimpleMerger rightSort = new SimpleMerger(right);
leftSort.sort();
rightSort.sort();
sorted = SimpleMerger.merge(leftSort.getSorted(), rightSort.getSorted());
}
}
public String[] getSorted() {
return sorted;
}
}
لفرز أجزاء الصفيف ، تم استخدام فرز جافا المضمن. التالي هو رمز الفرز باستخدام تجمع مؤشر ترابط. يتم إجراء قياسات الوقت للإصدارات متعددة الخيوط والتقليدية (المفسد: متعدد الخيوط يعطي التسارع فقط على كمية كبيرة من البيانات):
public static void main(String[] args) throws Exception {
int arrSize = 1_000_000_0;
String[] unsorted = new String[arrSize];
Random randomizer = new Random();
for ( int i = 0; i < arrSize; i++ ) {
unsorted[i] = Integer.toString(randomizer.nextInt( 100_000_0 ));
}
List<Future> futures = new ArrayList<>();
int processorCount = Runtime.getRuntime().availableProcessors();
int batchSize = arrSize/processorCount;
long startTime = System.currentTimeMillis();
final ExecutorService executorService = Executors
.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
ArrayList<Merger> mergers = new ArrayList<>();
for (int i = 0; i < processorCount; i++) {
String[] part = new String[batchSize];
System.arraycopy( unsorted, i*batchSize, part, 0, batchSize );
Merger merger = new Merger(part);
futures.add(executorService.submit(merger));
mergers.add(merger);
}
for (Future<Double> future : futures) {
future.get();
}
executorService.shutdown();
int j = 0;
String[] mergered = new String[arrSize];
for (Merger merger:mergers){
if (j == 0) {
mergered = merger.getSorted();
j+=1;
}
else{
String[] part = merger.getSorted();
mergered = SimpleMerger.merge( mergered, part);
}
}
long timeSpent = System.currentTimeMillis() - startTime;
System.out.println("Program execution time is " + timeSpent + " milliseconds");
if (arrSize < 100) {System.out.print(Arrays.toString(mergered));}
startTime = System.currentTimeMillis();
Arrays.sort(unsorted);
timeSpent = System.currentTimeMillis() - startTime;
System.out.println("\n Program (non parallel )execution time is " + timeSpent + " milliseconds");
}
في بداية الوظيفة الرئيسية ، تمتلئ المصفوفة بخطوط عشوائية تحتوي على أرقام من 0 إلى 10.000.000. يتم أخذ عدد مؤشرات الترابط على الجهاز كعدد مؤشرات الترابط. متغير batchSize مسؤول عن أبعاد المصفوفات للفرز بالتوازي. ثم يتم إنشاء خدمة تنفيذية بعدد ثابت من مؤشرات الترابط.لكل موضوع ، يتم إنشاء كائن دمج الفئة الخاص به ، ثم يضع هذا الموضوع مهمة الفرز في قائمة الانتظار للتنفيذ. بمساعدة المستقبل ، ننتظر حتى يتم حساب كل شيء ، وجمع جميع الأجزاء التي تم فرزها من الصفيف ودمجها بدوره في الصفيف الناتج. نوقف خدمة exoror ويمكن أن نلقي نظرة على تكاليف الوقت لتنفيذ متسلسل ومتوازي.الكود هنا