1. 4

    Why does this work?

    1. 13

      The graph is the colored directed graph with vertices 0, 1, 2, 3, 4, 5, 6 and the following rules

      • the white vertex is 0, all others are black
      • the black arrows connect k to (k+1)%7
      • the white arrows connect k to (10*k)%7

      So each vertex has two outgoing arrows, one black, one white.

      If you know the remainder of n modulo 7, this graph allows you to read off the remainders of n+1 and 10*n by following the black and white arrows emanating from the vertex n%7. An integer is divisible if and only if its remainder modulo 7 is 0.

      In the example given on the page, you calculate the remainder of 325 as follows:

      325 = ((3 *10 + 2) *10 + 5 = ((0+1+1+1) *10 +1+1) *10 +1+1+1+1+1.

      Start on the white vertex, follow three times a black arrow, then once a white arrow, twice a black arrow, once a white arrow then five times a black arrow and you land on vertex 3 = 325%7.

      1. 3

        What makes 7 special? Could I construct a similar graph for 5 or 11?

        1. 5

          There’s nothing special about 7 here. Except that it’s the first number for which all divisibility tests in base 10 are kinda tricky, so it’s neat that you can visualize one such test in a planar graph.

          You can define similar graphs G(b,m) for every base b>=2 and every modulus m>=1: the set of vertices is {0,...,m-1} and k is connected to (k+1)%m and (b*k)%m for each vertex k. Thus, the graph in the post is G(10,7).

          The author lists the planar graphs for small values of b and m in this comment.

          1. 1
      1. 3

        I’m really glad that it goes on to explain that there’s not really “no server”, and that it would probably would be more precise to call it “servermanagementless”

        1. 1

          “Managed hosting for platform X?”

          1. 1

            Thanks for the feedback.

            Yeah. Most people get confused when you say “serverless” and talk about the container being spawned. They’d be like: “Hmm. Pretty sure I see a server there :/” :D.

            Will post the talk video as soon as it gets uploaded.

          1. 12

            Still alive? Good. I have learned ins and outs of the Linux on HLFS and have very fond memories of it.

            1. 3

              Awesome. I’m planning to start with it.

              Are there any pre-reqs for taking this up?

              1. 4

                Are there any pre-reqs for taking this up?

                none, actually.

            1. 8

              I’m benchmarking an on-host historian for a SCADA controller.

              I’ll be comparing stock MySQL to MonetDB to this one this week

              1. 3

                Please blog and share it here, if you can. Would be a super interesting read :)

                1. 2

                  SO, the SCADA controller is PNNL’s product VoltTron, which has an extremely naive SQL schema for MySQL and SQLite. (Most users have very low demands for their historians, and they can upload their data in real time to something better, so no big deal.)

                  I installed MonetDB and used the same schema, and it choked. No surprise.

                  I put in a more sensible schema, and on queries beyond a certain length, it meats MySQL hands down.

                1. 1

                  Yeah, that should be the actual link (or better yet https://swtch.com/~rsc/regexp/), not this crappy article.

                  1. 12

                    Hi. Just wanted to share my slides about the topic :)

                    Sorry that you didn’t like the title (and/or) the slides! As it’s just a 15 mins talk, I was not able to cover more details (also cause I wanted to make this talk as understandable as possible to absolute beginners).

                    So, it can seem shallow to some folks here.

                    1. 4

                      i have no problem with the slides, but you really should include references to used sources if you more or less copy work of someone else!

                      1. 3

                        I did mention Russ Cox’s article in my talk. But yeah, thanks for the pointer. I’ll make sure I include the references in my slides too :)

                1. 1

                  And nobody’s ever complained that Perl’s algorithm has exponential run time?

                  1. 8

                    Most common regex matches are not pathological regexes, which means they don’t run for a painstakingly long time.

                    So, pathological regexes are a special case, and Perl do run exponentially on those. Also, please go through this discussion in the Perl forums, regarding the algorithm: http://www.perlmonks.org/?node_id=597364

                    1. 9

                      Perl and the others have good reasons for its choice. This talk does not mention the trade offs involved and only celebrates speedups for pathological cases. In short, the advantage of the PCRE approach is that it allows to add more features to the regex language.

                      1. 2

                        Good point. I wanted this talk to be for absolute beginners, so didn’t go into the details of the disadvantages of Thompson’s NFA and PCRE’s advantages :)

                        Having said that, Russ states in the article that the current features of the regex language are just abstractions, and can be done with the normal syntax (Backreferences being a useful exception).

                    2. 5

                      No-one has ever complained about Perl, ever. It’s the perfect language!

                      1. 4

                        You have to work hard to get it to behave badly; Perl understandably wants matching to be fast, and all of the ways to make it blow up with reasonable, useful code have been fixed sometime between 1987 and today.

                        1. 7

                          I think it’s more common than you think. StackOverflow had down time last year because of a backtracking regex.

                          1. 4

                            Yes, but they weren’t using Perl. If they were, that pattern would not have backtracked at all, and wouldn’t have caused any problem. The logic to avoid backtracking in that case was added in Perl 3.019 in 1990 — but .NET in 2016 is a different story :)

                            1. 1

                              How do I reason about when backtracking will occur and when it won’t?

                              1. 4

                                I don’t have a satisfying answer for that one.

                                It’s sort of like the halting problem vs. static code analysis thing. Everyone knows that you can’t statically analyze code behavior because the halting problem is unsolvable, and everyone knows that static analysis does work pretty good anyway because 99% of code in the real world does stuff that’s simple enough to analyze. You just need a big enough library of patterns and heuristics.

                                Well, regex matching with backtracking suffers from combinatorial explosion, except that 99% of regexes in the real world are simple enough that you can extract some feature from them that lets you rule out almost all possibilities and match them (or fail the match, since most problems usually occur on non-matching strings) immediately. A good regex engine will recognize and exploit those opportunities. But actually knowing exactly what bag of tricks your engine supports, recognizing when it doesn’t have your back anymore, and knowing how to fix it when that happens, is pretty much what separates the wizards from the average folks. There are some easy-to-learn cases (don’t unnecessarily nest quantifiers!), but a million more obscure ones.

                                1. 4

                                  Interestingly, us FSM regex proponents say something similar, “99% of all regexes you might want to write can be covered by a non-backtracking implementation, and when you hit a case where you want a more elaborate feature (look around or backreferences), you might be able to solve it with two regexes or maybe don’t use regex at all.” :-)

                                  I suspect the 99% numbers are phooey in both cases though.

                        2. 2

                          Most of the time regexes don’t backtrack much. The only time I’ve run into this was when I was writing a unit test in Java, and mistyped (complex)* as (complex)**. At the time, Java must have been naive about repeated *s, and tried all variants. The test ran for about a minute before timing out.

                        1. 1

                          Can someone please eli5 how Kubernetes does this, and if possible how Kubernetes works too :)

                          [Or maybe suggest some resources learning for the same]

                          1. 28

                            I’m not sure why this is share-worthy. What is the content here that people are upvoting? Not trying to be snarky - genuinely interested if there was something I missed.

                            1. 20

                              I’m not sure why this is share-worthy.

                              Not sure why it isn’t. It’s an interview about a [good] dev and an open-source maintainer, and the post fits perfectly under the person tag :)

                              1. 17

                                The title needs to be fixed to be more useful (is the link her personal site, a biography, some post about her?).

                                1. 9

                                  She has been one of the more consistently public, helpful, and relatable faces of Docker for years. Good presentations and demos.

                                  1. 22

                                    It’s not really that much about her, though, unfortunately.

                                    It reads like “docker kubermetes docker, a couple observations about open source, generic advice, plug for help for docker or kubermetes”. She seems like a perfectly nice person, but she doesn’t seem that much more noteworthy than any of a thousand other open-source developers paid to work on infrastructure projects. The interview doesn’t really cover anything personal about her, it doesn’t have her saying anything we haven’t heard a thousand times before or at least going in-depth on a story to explain her advice. The systemd->butts transform was amusing, to be sure, but otherwise why?

                                    I hate to be this, well, mean, but shouldn’t we be using the person tag for people of, well, note?

                                    ~

                                    And yes, this is kind of a core problem with the person tag. This person isn’t that interesting–given the information in the submission–to me, for example, but I could probably pick some alternate submissions that might be equally uninteresting (a person I know who is a greybeard at GOOG and has some cool projects.

                                    But where to draw the line without being petty? What makes articles under people good articles (instead of PR puff pieces)? Therein lies the rub.

                                    1. 10

                                      I get that anger is in your username and stuff but if you describe your own post as mean it’s probably not constructive.

                                      1. 5

                                        She is without question “of note” in the open source community. Especially in the infrastructure / “devops” space.

                                        If you don’t know her, maybe that’s not your thing?

                                        1. 9

                                          I think the problem here is that the interview doesn’t really say enough to convince someone that she’s worth interviewing. If you know her, you get it. If you don’t, then… we’ll, this isn’t helping, unfortunately.

                                          1. 3

                                            You’re right. Unfortunately, I don’t know that anyone who’s already “soaking in it” will take the time to write the “Hey, all you folks not in Devops, this is why Jesse is awesome!”.

                                            Maybe a little bit of open mindedness on people’s parts would help?

                                            1. 2

                                              Maybe a little bit of open mindedness on people’s parts would help?

                                              Yes! This is the key. We should probably trust our community a bit more than suggest an post with a decent number of points is irrelevant.

                                          2. 2

                                            Clearly not “without question”, right? Perhaps in the Docker/Kubermetes realm, but the article itself really doesn’t give much information about her, why she’s a big deal, or what she’s done. And that sucks, because people here are pointing out waaaay more interesting accomplishments she’s had.

                                            But again, the problem with the person tag is that you and I can both draft up a list of at least a half-dozen devs that are “of note” and yet the other one of us will go “huh?”. And in a few decades time, probably none of the people on those lists will be remembered.

                                            1. 2

                                              IMO it comes down to what people want this community to be about.

                                              I can totally see the angle where “person” violates the spirit of the place - what makes Lobsters great is all hardcore tech - all the time.

                                              I can also see the idea that showcasing awesome community contributors could be a good thing.

                                        2. 5

                                          The person tag is for stories about people, not profiles. A link to one of her talks, an in-depth or technical interview, or any one of a number of her blog posts would not have been flagged as off-topic.

                                          edit: I’ll also point out that in general the person tag is used alongside another tag. Cases of “person” alone are generally of some historical significance, an interview, or a death announcement; all of which are more substantive and/or better discussion topics than a simple profile.

                                        3. 5

                                          I’m with you. The title alone means nothing to me. I thought it was going to be some sort of memorial when I first saw it. But there isn’t really much of any content there. There’s nothing technical in it. I don’t understand what we’re meant to get from it.

                                          It fits HN more because that site is full of fluff like this, but I wouldn’t expect it here.

                                          1. 14

                                            I completely agree, this is not the kind of content I want to see here.

                                            1. 2

                                              FWIW this was only posted in here because it’s in the front page of HN. @av consistently posts whatever is popular there here (most of the time it makes sense, though).

                                              1. 4

                                                I like this content, but I don’t think that something reaching the front page of HN is a good litmus test for if it should be cross-posted here

                                            2. 4

                                              Lots of people don’t know where to start, and stories like this can be helpful. Lobste.rs has previously made similar pages for some of our users.

                                              1. 1

                                                Well, the community has voted for it so I guess you’ll just have to avoid clicking the link and move on then.

                                                1. 3

                                                  By the same argument tabloids are the best because there’s lots of demand for them!

                                              1. 1

                                                These would be quite handy for client-facing ML apps. Would love it if they enable encryption on these volumes too.

                                                1. 18

                                                  I’m really excited for this. I can’t wait to read the finished version.

                                                  Here’s a little anecdote. A few months ago I saw a comment by Bob (the author of this book) on Reddit, saying that he’s currently working on a book about interpreters. That got me super excited, because I was working on my own book about interpreters! Slightly intimidated that someone, who’s already written a great book, will be releasing a book about the same topic and maybe competing with me, I contacted Bob. I told him about my book and asked him if we’re essentially writing the same book. I was unsure about keeping on working on my book, now that there’s a pro tackling the same issues and covering the same niche. His reply couldn’t have been more motivating and encouraging, even if he tried. He essentially told me that I should keep working on my book, that there’s always room for more books and that he can’t wait to read it. I still think back to that email from time to time and credit it with giving me one of the many pushes needed to finish the book.

                                                  1. 7

                                                    Have you thought about making print copies of your book? I’ve been looking for an excuse to play around with Go, but I heavily favor the dead tree version. Either way, congrats on finishing it!

                                                    1. 8

                                                      Yes, I plan on releasing a print version in the next couple of months. Hopefully in February. I’ll send out a message on the mailing list, as soon as I know more. The major thing that’s holding me back is creating a print-proof cover image, that has the correct size, colors, resolution, margins, etc… That’s just not my area of expertise :)

                                                      1. 1

                                                        Please do! I just bought a digital copy after forgetting for a while, but I personally would be way more excited to shell out cash for something I can hold.

                                                    2. 4

                                                      Wow! Inspiring.

                                                      I’m learning Go myself, and this book really excites me.

                                                    1. 1

                                                      Just in case anyone is into reading papers for cluster/distributed systems, I think the following sources compile a better list:

                                                      https://roxanageambasu.github.io/ds2-class/2-papers/ http://courses.cs.washington.edu/courses/csep552/16wi/

                                                        1. 3

                                                          Interesting. I’m taking Nonlinear Optimization (taught by Steve Wright) and we give some theoretical analysis of these methods, but it’s nice to see the big picture with visualization.

                                                          1. 2

                                                            Great. Possible to share the link to the notes or video lectures (if any). I have gone through vanilla grad. descent, SGD and Mini-bathGD, and currently going through the Stochastic Average Gradient solver. Would love to dig deep into the topic.

                                                          1. 3

                                                            This is an interesting talk. If you already know about functional datastructures and B+-Trees, you can safely skip to the second half of the talk.

                                                            Here is the project he is talking about: https://github.com/datacrypt-project/hitchhiker-tree

                                                            1. 1

                                                              I found it very interesting.

                                                              Possible to share some links for learning(/getting started) about functional data structures?

                                                              1. 4

                                                                Check out Erik Demaine’s 6.851 material from his course on advanced data structures.

                                                            1. 3

                                                              This might not be a generalized problem. but anyway.

                                                              Python : Slow regex matching. If only Guido and co implemented the Thompson NFA algorithm for that (used in Unix tools like grep, awk, etc).

                                                              So, as an NLP engineer, I seek refuge in Go.

                                                              1. 2

                                                                You can install re2 from PyPI to get Thompson NFA regex.

                                                                1. 1

                                                                  Yeah, that’s there. I as just ranting :)

                                                                2. 2

                                                                  There is a drop-in replacement for re called regex which will hopefully replace it in future versions, with more features and faster performance. It doesn’t use NFAs but caching of some kind (I don’t fully understand it myself) to speed things up and reduce the chance of you accidentally creating pathological behaviour.

                                                                1. 6

                                                                  Anyone here have projects they run and need help on? While there is an official list, It would/could be nice to see what the rest of the community works on.

                                                                  1. 2

                                                                    The Gonum project is a project aimed to develop numeric computation and data science libraries for doing efficient and scalable data science in Go

                                                                  1. 2

                                                                    can we just post a link to russ' research blog and not repost each article individually?

                                                                    1. 1

                                                                      Wow. Thanks for the link :)

                                                                      I was re-directed to the Regexp posts from Go’s regexp docs. Didn’t know of Russ’s research blog :)

                                                                      1. 2

                                                                        you are welcome ;) the regexp series is really nice. maybe lobsters needs a feature for multiple links under one thread :)

                                                                    1. 4

                                                                      This is considered to be the bible of Deep Learning.

                                                                      In our reading group, we went through most of the book [1]. What is likeable is that it covers most of the techniques and theory pretty much up to the state of the art. What we disliked about the book is that it is quite badly organized. Some chapters do not have much of a logical progression. Also, it tends to dwell on trivial things, and goes over things that are more complex and important very quickly. (E.g., the sections on back-propagation are a good example of a suboptimal explanations)

                                                                      In the end, the book is a bit of a mixed bag. It’s great for machine learning practitioners - it treats most of the topics in NNs, but it’s not something that I’d recommend for an undergraduate or even a graduate course. I am still keeping my hopes up for Neural Networks and Deep Learning [2].

                                                                      [1] Note that we read a draft of 4-6 months ago. Our experience may not be completely relevant anymore. [2] http://neuralnetworksanddeeplearning.com

                                                                      1. 1

                                                                        Thanks for a nice review. So, what do you recommend to someone who have an understanding in Neural Nets (through Udacity’s ML Engg. nano-degree). for getting into Deep Learning?

                                                                        Books/(MOOC)Courses/any resources welcome.

                                                                        1. 2

                                                                          I think it depends on your goal. I can only reason from the perspective to someone who uses machine learning to contribute to another field (computational linguistics) and not as someone who is looking to contribute to the state of the art of machine learning.

                                                                          If your goal is similar (application of NNs), it’s very doable to do neural nets without diving head-first into theory. Some packages allow you to get started quickly, but still offer the possibility to build more complex graphs when you need to. Keras, in particular, has this property: simple networks are easy, complex networks can be done and are not hard. I also found that Keras' source code is easy to read to get a deeper understanding of the implementation. At some point interesting theory questions will definitely bubble up (why pick a ReLu over a hyperbolic tangent activation function? what is the difference between a GRU unit and LSTM unit? what is this unrolling business?). That’s a good point to read the relevant sections in Goodfellow’s book and/or look at the original literature.

                                                                      1. 1

                                                                        There is also this really good resource on ML and Deep Learning called the “A Course in Machine Learning by Hal Daumé III”. But, this is WIP for some chapter though.

                                                                        1. 9

                                                                          Not quite:

                                                                          “We have therefore decided that IPython 5.x will be the last major version to support Python 2.”

                                                                          The /next/ version, which has not been released yet, will no longer support Python 2.

                                                                          1. 1

                                                                            My bad! Thanks for spotting the mistake. Edited it :)