Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is meaningless:</p> <pre><code>case t:Map[Int, Map[Int, Y]] forSome { type Y } </code></pre> <p>because of erasure, all you can check for is this:</p> <pre><code>case t: Map[_, _] </code></pre> <p>which, in fact, is the only way you won't get warnings about erasure. Also, an existential type is almost always unnecessary, and, personally, I always find its syntax a bit tricky to get right. Still, this is the one case where using <code>_</code> to signify existential type is adequate. Note, however, that in my own code (the first version) I can't use it, because the types won't match if I do.</p> <p>Next,</p> <blockquote> <p>arbitrarily deep multi-dimensional arrays</p> </blockquote> <p>That's not a particular good idea. You must know what type you'll return to declare it -- if the deepness is "arbitrary", then so is the type. You can get away with a <code>Array[AnyRef]</code>, but it will be painful to use.</p> <p>Still, here is one way. I did away with all the loops, replacing them with map. Note where I take advantage of the fact that a <code>Map</code> is also a <code>Function1</code>, by calling <code>map m</code>. Note also that I just use <code>map</code> over an array (created with <code>toArray</code>) to avoid having to manage map creation.</p> <pre><code>def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = { def translate(x: AnyRef): AnyRef = x match { case map: Map[Int, AnyRef] =&gt; deMap(map) case s: String =&gt; s case other =&gt; throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString) } m.keys.toArray.sorted map m map translate } </code></pre> <p>There are two problems. To begin with, if the keys are not contiguous (<code>Map(0 -&gt; "a", 2 -&gt; "b")</code>, for example), the elements will be out of position. Here's a way around it, replacing the next to last line of code with:</p> <pre><code> Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate </code></pre> <p>Here I used an empty string to stand for any hole in the arrays.</p> <p>The other problem is that I assume all maps will be of type <code>Map[Int, AnyRef]</code>. To fix this, the could would have to be rewritten like this:</p> <pre><code>def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = { def translate(x: AnyRef): AnyRef = x match { case map: Map[_, _] =&gt; val validMap = map collect { case (key: Int, value: AnyRef) =&gt; (key -&gt; value) } deMap(validMap) case s: String =&gt; s case other =&gt; throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString) } Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate } </code></pre> <p>Here I discard all pairs whose keys aren't <code>Int</code> and values aren't <code>AnyRef</code>. One could further safe-check the code to test if something's missing and report and error in that case:</p> <pre><code>def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = { def translate(x: AnyRef): AnyRef = x match { case map: Map[_, _] =&gt; val validMap = map collect { case (key: Int, value: AnyRef) =&gt; (key -&gt; value) } if (map.size &gt; validMap.size) { val wrongPairs = map.toSeq diff validMap.toSeq throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs) } deMap(validMap) case s: String =&gt; s case other =&gt; throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString) } Array.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate } </code></pre> <p>Finally, about performance. Using <code>map</code> the way I did means a new array will be allocated for each <code>map</code>. Some people take that to mean I have to iterate three times instead of one, but since each time I do a different task, it isn't really doing much more work. However, the fact that I allocate a new array each time definitely has performance impact -- both because of the allocation penalty (Java pre-initializes all arrays), and because of cache locality concerns.</p> <p>One way to avoid that is using a <code>view</code>. When you do <code>map</code>, <code>flatMap</code> and <code>filter</code> over a <code>view</code>, you get a new view back, with that operation <em>stored</em> for future use (other methods might work that way too -- check the documentation, or test when in doubt). When you finally do an <code>apply</code> on the <code>view</code> object, it will apply all the operations necessary to get the specific element you have asked for. It will do so every time you <code>apply</code> for that element too, so performance can be both better or worse.</p> <p>Here I'll start with a <code>Range</code> view, to avoid array allocation, and then convert the view to an <code>Array</code> at the end. Still, <code>keys</code> will create a set, imposing some overhead. After this I'll explain how to avoid that.</p> <pre><code>def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = { def translate(x: AnyRef): AnyRef = x match { case map: Map[_, _] =&gt; val validMap = map collect { case (key: Int, value: AnyRef) =&gt; (key -&gt; value) } if (map.size &gt; validMap.size) { val wrongPairs = map.toSeq diff validMap.toSeq throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs) } deMap(validMap) case s: String =&gt; s case other =&gt; throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString) } (0 to m.keys.max view) map (m getOrElse (_, "")) map translate toArray } </code></pre> <p>You should leave <code>view</code> to necessary optimizations, however, instead of pro-actively using them. It isn't necessarily faster than normal collections, and its non-strictness can be tricky. Another alternative to using <code>view</code> is using a <code>Stream</code> instead. A <code>Stream</code> is much like a <code>List</code>, except it only computes it's elements on demand. That means none of the <code>map</code> operations will be applied until necessary. To use it, just replace the next to last line to this:</p> <pre><code> Stream.range(0, m.keys.max + 1) map (m getOrElse (_, "")) map translate toArray </code></pre> <p>The main advantage of a <code>Stream</code> over a <code>view</code> is that once a value in a <code>Stream</code> has been computed, it stays computed. That is also it's main disadvantage over a <code>view</code>, ironically enough. In this particular case, I think <code>view</code> is faster.</p> <p>Finally, about doing a <code>max</code> without computing a <code>Set</code> (the result of <code>keys</code>) first. A <code>Map</code> is also an <code>Iterable</code>, and all <code>Iterable</code> have a <code>max</code> method, so you can simply do <code>m.max</code>. That, however, will compute the max of <code>Tuple2[Int, AnyRef]</code>, a type for which there is no <code>Ordering</code>. However, <code>max</code> receives an implicit parameter telling it what <code>Ordering</code> to use, which can be thus provided:</p> <pre><code>m.max(Ordering by ((_: (Int, AnyRef))._1)) </code></pre> <p>This is a bit of a mouthful, so we can define the implicit we need and use it, err, implicitly. :-)</p> <pre><code>def deMap(m: Map[Int, AnyRef]): Array[AnyRef] = { implicit val myOrdering = Ordering by ((_: (Int, AnyRef))._1) def translate(x: AnyRef): AnyRef = x match { case map: Map[_, _] =&gt; val validMap = map collect { case (key: Int, value: AnyRef) =&gt; (key -&gt; value) } if (map.size &gt; validMap.size) { val wrongPairs = map.toSeq diff validMap.toSeq throw new IllegalArgumentException("Invalid key/value pairs found: "+wrongPairs) } deMap(validMap) case s: String =&gt; s case other =&gt; throw new IllegalArgumentException("Expected Map or String, got "+other.getClass.toString) } (0 to m.max._1 view) map (m getOrElse (_, "")) map translate toArray } </code></pre> <p>Note that <code>max</code> returns a tuple, <code>key</code> and <code>value</code>, so we need <code>_1</code> to get the <code>key</code>. Also, note that we create an <code>Ordering</code> object at each nesting of <code>deMap</code>. Not bad, but it could be made better by defining it elsewhere.</p> <p>Once you have done all that, a <code>while</code> loop will still be faster, though I have no idea by how much. Given enough JVM optimizations, they might come pretty close. On the other hand, if you <em>really</em> want speed, you could go all the way to assembler code. It comes down to a balance between how easy and fast it is to write the code, how easy it is to maintain it, and how fast it runs.</p>
    singulars
    1. This table or related slice is empty.
    1. POrecursively convert Map[Int, Map[Int, X]] to Array[Array[X]]
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDaniel C. Sobral
    1. USDaniel C. Sobral
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POrecursively convert Map[Int, Map[Int, X]] to Array[Array[X]]
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks! Interesting point about erasures, and your code is much more elegant than mine. How does the "toArray" + "map" compare in speed to the while loops? Also, you said: "You must know what type you'll return to declare it." I hoped that by using higher-order types (which seem like magic to me at the moment) I could avoid making a new "deMap" function for each depth; but seeing the "ofDim" methods in the companion object for Array in the scala API has convinced me otherwise.
      singulars
      1. PO
      1. USdsg
    2. CO@dsg I extended the answer with comments about performance.
      singulars
      1. PO
      1. USDaniel C. Sobral
    3. COWow, this is a fantastic answer! I learned a lot, thank you very much.
      singulars
      1. PO
      1. USdsg
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload