Wikipedia:Reference desk/Archives/Computing/2016 August 20

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 20

Python question about Trie implementation

class Node:
    def __init__(self, children = {}):
        self.children = children

    def insert(self, target):
        # If nothing left to insert then we are done
        if len(target) < 1:
            return

        firstLetter = target[0]
        if firstLetter in self.children:
            self.children[firstLetter].insert(target[1:])
        else:
            newNode = Node()
            newNode.insert(target[1:])
            self.children[firstLetter] = newNode # The problem is this line

root = Node()
root.insert("a")

I'm trying to write a simple trie implementation in Python but ran into this simple bug that I, embarrassingly enough, can't even find. My insert function has a bug that the newly inserted Node contains a pointer that point to itself, creating an infinite loop. Any and all help or suggestions are greatly appreciated. Pizza Margherita (talk) 05:04, 20 August 2016 (UTC)

You might try the Wikipedia Computing Reference Desk where you are more likely to find somebody who understands this sort of thing. The Language Ref Desk is really about languages that humans can speak. Alansplodge (talk) 09:32, 20 August 2016 (UTC)

I thought that this is the Computing Reference Desk? It says "Wikipedia:Reference desk/Computing" at the top of the page. Apologies if I got it wrong. Pizza Margherita (talk) 16:53, 20 August 2016 (UTC)

This is the Computing RD, no worries. I don't pretend to understand what's going on, but it seems that if newNode is instantiated explicitly with an empty dict() as newNode = Node(children={}), then things work. With the original code, when you instantiate a second Node, root2 = Node(), after inserting something into root, then root2 immediately has the same children as root. --Wrongfilter (talk) 19:57, 20 August 2016 (UTC)

Pizza Margherita you're in the right place, I think Alansplodge just had a moment. :) RegistryKey^(RegEdit) 19:55, 20 August 2016 (UTC)

D'oh! Alansplodge (talk) 00:08, 21 August 2016 (UTC)

This is a standard trap: your constructor has a default parameter value that is a mutable object — the same dictionary for every call. --Tardis (talk) 20:13, 20 August 2016 (UTC)

Ah, thanks a lot. Pizza Margherita (talk) 20:32, 20 August 2016 (UTC)

Resolved

Hardware differences between different USB type-A versions

I wonder if the differences between different USB type-A versions (e.g. 3.0 to 3.1) include any hardware changes or if only the protocol was updated. If so, what changes exactly were made? Different alloy? Different arrangement of pins?

I've tried reading the article but it's too technical for me. Thanks! OP / 16:32, 20 August 2016 (UTC) — Preceding unsigned comment added by 84.108.121.108 (talk)

From what the articles state, USB 3.1 gen 2 is twice as fast as USB 3.0, so I would assume that the bus itself would have been changed out in terms of hardware. RegistryKey^(RegEdit) 20:05, 20 August 2016 (UTC)

If I'm interpreting it correctly, they didn't change any of the hardware. They just changed the line code. USB 3.0 uses 8b/10b, while 3.1 uses the newer 128b/132b encoding. The latter has more than five times less overhead. --71.110.8.102 (talk) 08:06, 21 August 2016 (UTC)

As indicated by RegEdit, USB 3.1 gen 2 SuperSpeed is capable of 10 Gbps while USB 3.0 only 5 Gbps. 8b/10b is only 20% overhead so isn't even half of the difference. I don't know precisely what transmission difference account for the rest of the speed increase, but I'm unclear what the OP means by "hardware changes" or "only the protocol was updated" anyway (and I'm not sure if the OP really understands how things change, I don't really amd I don't find out article that technical). With differing demands on the cable and ports, it's possible or even probable that there was a tightening of the spec e.g. [1] [2] [3] [4]. So a raw cable fully compliant with USB 3.0 may not comply with the USB 3.1 gen 2 spec. However some or even most cables may very well do so although if I'm understanding the first two links correctly four grounding springs and tabs are now required so I guess the connectors and finished cables will be far less likely to be compliant. There was increase in the number of pins from USB 2.0 high speed to USB 3.0 super speed but not since then. I'm not sure if the USB spec even specifies what the cable needs to be made of, although maybe it does since the ISO/IEC and EIA/TIA both specify copper for most categories of ethernet cables. Meaning there's no such thing as Cat 5 copper-clad aluminium cable for example as even if it complies with all other characteristics it's still not compliant [5] [6] [7]. Nil Einne (talk) 14:43, 21 August 2016 (UTC)

P.S. Since maybe part of the above it too complicated for the OP. My point is that I guess the addition of the grounding springs and tabs would be considered a "hardware change" so by that token there was clearly a "hardware change" from USB 3.0 to USB 3.1 gen 2. Just as there was from USB 2.0 to USB 3.0 with the additional connections (pins and wires). But what about tightened impedance, losses at different frequencies and other requirements of the cables etc required by the new spec? Is this a "hardware change"? I think you need to have some understanding of how higher speeds are achieved before you can begin to understand any answer to these sort of questions. Notably, as I indicated, the spec may not even say what sort of material should be used. In the case of USB these may also be because of different power requirements instead of simply the speed changes. Nil Einne (talk) 05:55, 22 August 2016 (UTC)

If the question is "Can I plug a 3.0 device into a 3.1 port and vice versa, and expect it to just work" I think the answer is yes. All the best: Rich Farmbrough, 16:52, 22 August 2016 (UTC).