समस्या का पृष्ठभूमि: मैं एक पहेली समाधान एल्गोरिदम लिखने की कोशिश कर रहा हूं जो बहु-कोर प्रोसेसर और समांतर प्रसंस्करण का लाभ उठाता है। हालांकि, आदर्श/सबसे आसान समाधान एक सरल पुनरावर्ती समारोह है।पुनरावर्ती कार्यों के साथ समांतर प्रोग्रामिंग?
समांतर प्रसंस्करण और रिकर्सिव फ़ंक्शन का लाभ लेने के लिए समाधान को तोड़ने का सबसे अच्छा तरीका क्या है?
नीचे दिया गया कोड एक सरल पहेली सुलझाने वाले एल्गोरिदम के लिए एक समाधान है (यह सही ढंग से काम करता है)। इस उदाहरण में पहेली सरल है - 14 स्लॉट संख्या 1-14 है। प्रत्येक पहेली टुकड़े में एक अनूठी आईडी होती है, एक सीमा जो आपको बताती है कि यह कहां से शुरू हो सकती है और रोक सकती है (उदाहरण के लिए 6-8 का मतलब है कि यह केवल स्लॉट 6-8 में फिट बैठता है), और एक मूल्य। एल्गोरिदम समाधान खोजने की कोशिश करता है जो समाधान की कीमत को अधिकतम करता है। केवल 1 टुकड़ा एक स्लॉट पर कब्जा कर सकता है, और खाली स्लॉट स्वीकार्य हैं। समाधान आपको बताएगा कि कौन से टुकड़े उपयोग किए जाते हैं और कुल लागत। (चीजों को सरल रखने के लिए, मान लें कि स्लॉट 1 भरना होगा)।
समांतरता और पुनरावर्तन को गठबंधन करने का मेरा प्रयास समाधान नीचे उपयोग किया जाता है: स्लॉट 1 का उपयोग करने वाले प्रत्येक टुकड़े के लिए एक कार्य बनाएं, फिर कार्य के भीतर शेष टुकड़ों को फिर से देखें, उन्हें अधिकतम रिक्त स्थान पर रखें जबकि अधिकतमकरण कीमत। क्या यह सबसे अच्छा समाधान है (शायद नहीं, यही कारण है कि मैं यहां हूं)। इसमें कैसे सुधार किया जा सकता है? समांतर/पुनरावर्ती समाधानों का उपयोग करते समय कोई और अच्छी सिफारिशें?
जबकि सरल रिकर्सन यहां अच्छा काम करेगा, मैं इसे एक पहेली के साथ चल रहा हूं जिसमें 200 स्लॉट और 5000 टुकड़े हैं।
यहां इस उदाहरण का हल है साथ ही:
ID=1 Price=10.0 Range=1-6
ID=12 Price=8.0 Range=9-14
ID=15 Price=3.0 Range=7-8
public class Puzzle
{
public PuzzleSet calculateResults(PuzzleSet input) throws Exception
{
System.out.println(System.currentTimeMillis());
PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input));
System.out.println(System.currentTimeMillis());
return results;
}
private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception
{
PuzzleSet initial = input.startsAtPoint(1);
ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1);
Collection<Callable<PuzzleSet>> tasks = new ArrayList<Callable<PuzzleSet>>();
for (int i=0; i<initial.size(); i++)
{
final PuzzleData d = initial.get(i);
final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper);
tasks.add(new Callable<PuzzleSet>() {
public PuzzleSet call() {
PuzzleSet s = new PuzzleSet();
s.add(d);
s.addAll(getPrice(start));
return s;
}
});
}
List<Future<PuzzleSet>> results = exec.invokeAll(tasks);
PuzzleSet max = new PuzzleSet();
double maxD = 0.0;
for (int i=0; i<results.size(); i++)
{
PuzzleSet temp = results.get(i).get();
double sum = temp.sum();
if (sum > maxD)
{
maxD = sum;
max = temp;
}
}
return max;
}
private PuzzleSet getPrice(PuzzleSet input)
{
if (input == null || input.size() == 0) return new PuzzleSet();
double maxD = 0.0;
PuzzleSet max = new PuzzleSet();
for (int i=0; i<input.size(); i++)
{
PuzzleSet vs = input.higherThan(input.get(i).rangeUpper);
PuzzleSet s = getPrice(vs);
double d = s.sum();
double pTemp = input.get(i).price + d;
if (pTemp > maxD)
{
maxD = pTemp;
s.add(input.get(i));
max = s;
}
}
return max;
}
public static void main(String arg[]) throws Exception
{
PuzzleSet s = new PuzzleSet();
PuzzleData v1 = new PuzzleData();
v1.rangeLower = 1;
v1.rangeUpper = 6;
v1.price = 10;
v1.ID = 1;
s.add(v1);
PuzzleData v2 = new PuzzleData();
v2.rangeLower = 7;
v2.rangeUpper = 11;
v2.price = 0;
v2.ID = 2;
s.add(v2);
PuzzleData v3 = new PuzzleData();
v3.rangeLower = 12;
v3.rangeUpper = 14;
v3.price = 7;
v3.ID = 3;
s.add(v3);
PuzzleData v5 = new PuzzleData();
v5.rangeLower = 7;
v5.rangeUpper = 9;
v5.price = 0;
v5.ID = 4;
s.add(v5);
PuzzleData v6 = new PuzzleData();
v6.rangeLower = 10;
v6.rangeUpper = 14;
v6.price = 5;
v6.ID = 5;
s.add(v6);
PuzzleData v7 = new PuzzleData();
v7.rangeLower = 1;
v7.rangeUpper = 3;
v7.price = 5;
v7.ID = 6;
s.add(v7);
PuzzleData v8 = new PuzzleData();
v8.rangeLower = 4;
v8.rangeUpper = 9;
v8.price = 0;
v8.ID = 7;
s.add(v8);
PuzzleData v10 = new PuzzleData();
v10.rangeLower = 1;
v10.rangeUpper = 5;
v10.price = 3;
v10.ID = 8;
s.add(v10);
PuzzleData v11 = new PuzzleData();
v11.rangeLower = 6;
v11.rangeUpper = 11;
v11.price = 2;
v11.ID = 9;
s.add(v11);
PuzzleData v12 = new PuzzleData();
v12.rangeLower = 12;
v12.rangeUpper = 14;
v12.price = 7;
v12.ID = 10;
s.add(v12);
PuzzleData v14 = new PuzzleData();
v14.rangeLower = 4;
v14.rangeUpper = 8;
v14.price = 1;
v14.ID = 11;
s.add(v14);
PuzzleData v15 = new PuzzleData();
v15.rangeLower = 9;
v15.rangeUpper = 14;
v15.price = 8;
v15.ID = 12;
s.add(v15);
PuzzleData v16 = new PuzzleData();
v16.rangeLower = 1;
v16.rangeUpper = 5;
v16.price = 3;
v16.ID = 13;
s.add(v16);
PuzzleData v17 = new PuzzleData();
v17.rangeLower = 6;
v17.rangeUpper = 8;
v17.price = 1;
v17.ID = 14;
s.add(v17);
PuzzleData v18 = new PuzzleData();
v18.rangeLower = 7;
v18.rangeUpper = 8;
v18.price = 3;
v18.ID = 15;
s.add(v18);
PuzzleSet x = new Puzzle().calculateResults(s);
for (int i=0; i<x.size(); i++)
{
System.out.println(x.get(i));
}
}
}
public class PuzzleData implements Serializable
{
public int rangeLower;
public int rangeUpper;
public int ID;
public double price;
public String toString()
{
return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper;
}
}
public class PuzzleSet extends ArrayList<PuzzleData> implements Serializable
{
public PuzzleSet higherThan(int lowBound)
{
PuzzleSet s = new PuzzleSet();
for (int i=0; i<size(); i++)
{
if (get(i).rangeLower > lowBound)
s.add(get(i));
}
return s;
}
public PuzzleSet startsAtPoint(int point)
{
PuzzleSet s = new PuzzleSet();
for (int i=0; i<size(); i++)
{
if (get(i).rangeLower == point)
s.add(get(i));
}
return s;
}
public double sum()
{
double sum = 0.0;
for (int i=0; i<size(); i++)
sum += get(i).price;
return sum;
}
public String toString()
{
StringBuffer b = new StringBuffer();
for (int i=0; i<size(); i++)
{
b.append(get(i).toString());
}
return b.toString();
}
}
+1। यद्यपि यह एक भौं-उठाने वाला डोमेन नाम है! – Bolo
लिंक के लिए धन्यवाद। 1.5 या बेहतर में अभी तक किसी भी तीसरे पक्ष के पुस्तकालयों के बारे में जानते हैं जो अब करते हैं? – bluedevil2k
जेएआरके 1.5 को हाल ही में जेएसआर -166 में अपग्रेड करने के लिए जेएआर http://gee.cs.oswego.edu/dl/concurrency-interest/index.html पर डाउनलोड किया जा सकता है ... – meriton