Difference between revisions of "Slices"

From CSE231 Wiki
Jump to navigation Jump to search
 
(40 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
This assignment has been replaced by [[Ranges]].
 +
<!--
 +
 +
credit for this assignment: Finn Voichick and Dennis Cosgrove
 +
 
=Motivation=
 
=Motivation=
−
Coarsening, or n-way split as we tend to call it in this course, comes up a fair amount.  This studio has you implement a utility that you can use over and over throughout the semester.
+
Coarsening, or n-way split as we tend to call it in this course, comes up a fair amount.  In this studio, we will create our Slices class, that allows us to split up our data n-times (depending on what value we pass in) in a consistent organized fashion. This makes sure that each thread is balanced in the work that it does, minimizing the Critical Path Length.
−
 
 
−
In order to support future testing well, we are strict about exactly how the data is split up among the slices.
 
  
−
=Java Utility=
+
Since we will be utilizing this class throughout the semester in different studios and assignments, it is important that data is split up in a specific way. The tests should help make sure your solution is in working order.
−
In order to conveniently support primitive arrays and Object arrays we will need to use the [https://docs.oracle.com/javase/8/docs/api/java/lang/reflect/Array.html#getLength-java.lang.Object- Array.getLength(Object)] method.
 
  
 
=Mistakes To Avoid=
 
=Mistakes To Avoid=
 
{{warning | Do NOT Parallelize}}
 
{{warning | Do NOT Parallelize}}
  
−
{{warning | Do NOT Copy The Data Into SubArrays}}
+
This studio is about creating an easier way to split data so that it can be worked on in parallel. The splitting of the data is still done sequentially. That means at no point in this studio should you be using async() or finish().
  
−
=Background=
+
=Code To Investigate=
 +
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html class IndexedRange]
 +
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#%3Cinit%3E(int,int,int) constructor].
  
−
As the name suggests, we will create a class to represent a <code>Slice</code> of data and a list of <code>Slice</code> called <code>Slices</code> which divides the data into a specified number of <code>Slice</code> given an array of data.
+
<pre>public IndexedRange(int sliceIndexId, int minInclusive, int maxExclusive)</pre>
  
−
=Where to Start=
+
This class has everything you need for [[Nucleobase_Counting#Coarsening_N-Way_Split|n-way split]] problems, specifically: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getSliceIndexId() getSliceIndexId()], [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getMinInclusive() getMinInclusive()], and [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getMaxExclusive() getMaxExclusive()].
  
−
Navigate to the slice directory and look under <code>slice.studio</code>. You must implement <code>Slices</code> using the implementation of <code>Slice</code> given to you under the <code>slice.core</code> directory.
+
=Code to Implement=
 +
{{CodeToImplement|Slices|createNSlices|slices.studio}}
  
 
==createNSlices==
 
==createNSlices==
  
−
To create this slice, you will start at the beginning of the data array and keep creating new slices until you have numSlices which more or less evenly span the range. Remember that the sliceId should start at the zero index and the length of the list should be equal to the number of slices. Also remember that if the range is not divisible by numSlices, you must account for this by either evenly distributing the extras or making a slightly larger slice at the end of the range.
+
{{Sequential|public static List<IndexedRange> createNSlices(int minInclusive, int maxExclusive, int numSlices)}}
 +
 
 +
Given a range [minInclusive, maxExclusive) and a number of slices to make, return a List of IndexedRanges. Understanding what a IndexedRange is and how it is used is important when writing this solution.
 +
 
 +
The goal is to have each slice's range be the entire array when put together, with no overlap. Some examples are giving below. Working through more examples can be a helpful way of figuring out what code to write if you get stuck.
 +
 
 +
{{ tip | In a slice, the minimum is inclusive and the maximum is exclusive.  This means for two slices next to each other, slice1.getMaxExclusive() is equal to slice2.getMinInclusive(). }}
 +
 
 +
==Strict Specification==
 +
We are overly strict about the specification of how the data '''must''' be sliced up.  This is to allow to accurately compare results intermediate results throughout the semester.
 +
 
 +
'''Example: array.length=8; numSlices=4'''
 +
 
 +
{| class="wikitable"
 +
|A
 +
|A
 +
|B
 +
|B
 +
|C
 +
|C
 +
|D
 +
|D
 +
|}
 +
 
 +
{| class="wikitable"
 +
|-
 +
!Slice ID !! Min Inclusive !! Max Exclusive
 +
|-
 +
|0 || 0 || 2
 +
|-
 +
|1 || 2 || 4
 +
|-
 +
|2 || 4 || 6
 +
|-
 +
|3 || 6 || 8
 +
|}
 +
 
 +
 
 +
 
 +
'''Example: array.length=7; numSlices=4'''
 +
 
 +
Distribute the remainder 1 each to the lower end slices (the first few slices or the lower index slices).
 +
 
 +
{| class="wikitable"
 +
|A
 +
|A
 +
|B
 +
|B
 +
|C
 +
|C
 +
|D
 +
|}
 +
 
 +
{| class="wikitable"
 +
|-
 +
!Slice ID !! Min Inclusive !! Max Exclusive
 +
|-
 +
|0 || 0 || 2
 +
|-
 +
|1 || 2 || 4
 +
|-
 +
|2 || 4 || 6
 +
|-
 +
|3 || 6 || 7
 +
|}
 +
 
 +
{{Warning|Do NOT slice up the data by giving all of the remainder to one slice}}
 +
<s>
 +
A
 +
|B
 +
|C
 +
|D
 +
|D
 +
|D
 +
|D
 +
</s>
 +
 
 +
Giving all the remainder to one slice defeats the purpose of balancing the workload!
 +
 
 +
==Convenience Methods==
 +
 
 +
In order to support primitive arrays (e.g. byte[], int[], et cetera) and non-primitive arrays (e.g. Object[]) we provide all of the public methods, each which simply call the single method requiring implementation:
 +
 
 +
<nowiki> public static <C> List<IndexedRange> createNSlices(C[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(byte[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(char[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(short[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(int[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(long[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
 +
 
 +
public static List<IndexedRange> createNSlices(float[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}
  
−
Hint: you do not need to divide up the array of data fed into the method and doing so would remove the need for a <code>minInclusive</code> variable for a <code>Slice</code>.
+
public static List<IndexedRange> createNSlices(double[] data, int numSlices) {
 +
return createNSlices(0, data.length, numSlices);
 +
}</nowiki>
  
−
=Javadocs=
+
=Testing Your Solution=
−
implement: [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/slice/studio/Slices.html#createNSlices-T:A-int- Slices.createNSlices method]
+
==Correctness==
 +
{{TestSuite|SlicesTestSuite|slice.studio}}
  
−
use: [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/slice/core/Slice.html class Slice]
+
=Pledge, Acknowledgments, Citations=
 +
{{Pledge|studio-slices}}
 +
-->

Latest revision as of 21:56, 30 November 2022

This assignment has been replaced by Ranges.

Retrieved from "http://classes.engineering.wustl.edu/cse231/core/index.php?title=Slices&oldid=4155"