Header logo.
small hallucinations
homeyearstagsaboutrss

A bug in CRA and time complexity of list and set operations

Here are a few things I noticed in week 7.

I was creating a React app using create-react-app and ran into this error:

You are running 'create-react-app' 4.0.3, which is behind the latest release (5.0.0).

After googling around I saw a workaround by installing v5 locally.

Yet a better workaround is:

npx [email protected] app-name

Update on Feb 24

Should have read the thread more closely, because clearing npx cache should do: npx clear-npx-cache.


I was reading Ace the Data Science Interview and there's a chapter about coding.

One easy coding problem reads:

Given two arrays, write a function to get the intersection of the two.

I guess to show your ingenuity, you are not supposed to use sets, which are native to Python.

The most naïve idea is to run a doubly nested for loop to check each item in arr_n against each item in arr_m. That way, the time complexity would be O(n*m).

A twist on this idea is to run a for loop to iterate through the shorter array (arr_n) and check if arr_n[i] exists in the longer array (arr_m). By doing so, the time complexity is also O(n*m) because the average case time complexity to find an item in arr_m is O(m). (I had mistakenly thought checking existence of an item costs O(1).)

A simpler solution is using sets. The official solution given in the book first converts the two arrays to sets. Then checks which items in the shorter set exist in the longer set by doing this:

[x for x in set_n if x in set_m] (time complexity O(n))

The time complexity of this solution in total is O(n) + O(m + n), because converting lists to sets costs O(n) too, and we have two arrays here. Less than O(n*m).

At first I wondered why they didn't directly use set intersection. I guess that's because converting the resulting set back to a list would cost another O(len(intersection)).

Method list.sort() vs function sorted()

The more I program, the more I find myself realizing the why of some of the basics.

You can use either a method or a function to sort or reverse a list in Python. One works in-place, meaning the order of items in the original list is changed. The other works on a copy of the list and returns an ordered version of that copy as a new list.

list.sort() and list.reverse() are methods of the list class. They are both verbs, suggesting they take actions on an instance of the list class. And as methods that are internal to a list, they are understandably “allowed” to change the internal order of list items.

sorted() and reversed() are functions external to the list class. They are both adjectives. If a function tampers with the data passed in as an argument, that makes it not a pure function. So in functional programming terms, they are both pure functions.

Week 47

I spent some time last week to get myself more familiar with TypeScript.

Although I'd known the syntax, how to type things (props, components, etc) was at times still confusing. I probably saw more than a bunch of errors thrown at me.

Hopefully I'd love it when I get the hang of it. People on the internet say, all pros and cons considered, it's worth the while.

Week 46 gave me surprises

A few things:

Handling date and time is more complicated than I expected. python-dateutil is quite helpful when you need to parse a datetime string.

A pitfall

I tried updating a field in a MongoDB document using MongoEngine. The value of that field was an embedded document that contained four sub-fields. I intended to change the value of subkey2. But the entire embedded document was overwritten.

 1{
 2    key1: value1,
 3    key2: value2,
 4    key3: {
 5        subkey1: subvalue1,
 6        subkey2: subvalue2,
 7        subkey3, subvalue3
 8    }
 9
10    # After updating, this field instead became this...
11    # ...and this is not what I wanted
12    key3: {
13        subkey2: newvalue
14    }
15}

I'm quite glad I caught this potential bug early on. And indeed, smart people out there have figured it out.

Baffling decimals

I was trying to check if the submitted value and the value found in MongoDB are the same. This field was defined as a decimal.

In order to try it out, I artificially submitted a JSON object that contained a number with two decimal places (69.30) and the value I saved in MongoDB was 69.3 of decimal type (or I thought so).

But Decimal(submitted_value) == Decimal(mongodb_value) returned False.

Printing out the two values, I got:

1# submitted_value
269.30 
3# mongodb_value
469.299999999999997157829056...

The reason of this turned out to be: Although I defined this field to be a DecimalField with precision=2 in MongoEngine, the value actually stored in MongoDB was still a Double.

And a float number is supposed to do this.

So much fun in week 45

These are the fun I had in week 45, 2021.

Djongo

I ended up in a situation where I decided to use Djongo to bridge MongoDB and Django.

MongoEngine team made a Django connector. But it does not seem to be actively maintained. So they pointed to Djongo and described it as “promising”. (Spoiler: If something is “promising”, the universe hasn't decided whether to resolve it or reject it.)

It seemed as if the only thing you needed to do is go to settings.py and change the database engine to Djongo like so.

 1DATABASES = {
 2    'default': {
 3        'ENGINE': 'djongo',
 4        'NAME': '<db_name>',
 5        'ENFORCE_SCHEMA': True,
 6        'CLIENT': {
 7            'host': '<conenction_url>'
 8            }
 9    }
10}

If you set enforce schema to True, you'd need to run migrations like dealing with a relational DB. Setting this parameter to False would save you some hassle.

Then an error popped up saying a certificate was required. (SSL: CERTIFICATE_VERIFY_FAILED) Djongo's documentation mentioned in passing that you could use arguments allowed in pymongo.MongoClient().

In this case, useful arguments were ssl, ssl_cert_reqs and ssl_ca_certs. But Djongo doc did not tell you how exactly you could do that.

After some trial and error, I did the obvious by directly adding query params to the URL.

  • 'ssl=true&ssl_cert_reqs=CERT_NONE'
  • 'ssl=true&ssl_ca_certs=' + certifi.where()

The first one is less secure. To use an actual certificate, you need to install certifi and go with the second. (There were more trials and errors. And a lot of times, doing the obvious didn't work.)

Maybe I'm overthinking, but...

At some point I wrote this code for an endpoint that expected a JSON object with keys username and password. (Remember destructuring assignment from JavaScript? LOL!)

1def auth_login(request):
2    username, password = json.loads(request.body.decode()).values()
3    # Surely this will work right?

I soon realized nothing prevented the client from uploading something like this:

1{
2    "password": "pa$sw0rd",
3    "username": "lexie"
4}

And since this was not JavaScript, we'd end up with username being pa$sw0rd and password being lexie.

And git ignores case by default

It seems quite a few people don't know git by default ignores case.

I learned this because I once mistakenly named the file for a React component in lowercase then imported it using the capitalized filename.

This could be a problem if you misname a Procfile or a Dockerfile. And you actually don't need to recreate the entire repository like Matt did in this video.

Set ignorecase to false like this and rename the file. A learn this solution (of course) from a note on StackOverflow.

1git config --local core.ignorecase false

Reading Books in Swedish

It took me more than a year to finish reading my first Swedish novel Tio över ett, a teenage romance story set in mining town Kiruna. I got this paperback from a shelf at Uppsala University where people leave their used books. You'd most often see conference proceedings and PhD dissertations – dozens of brand new copies at once – left there.

I also bought the audio version from Bokus.com, because you can download DRM-free MP3 files from there.

Once you have the MP3 files, you can practice dictation with them. It's handy to listen to the recordings using a piece of audio software, such as Audacity or Tenacity.

The idea is: First you read the text and look up new words when you feel like to. Don't worry too much about missing key points in the plot. Think of your brain as a machine learning algorithm. By feeding language data (text and voice) into it, assuming you have an adequate grasp of Swedish grammar, your brain will work out how this language works.

Then you practice listening by writing down every word you hear. This takes enormous amount of time. So you don't need to do the whole book. You probably don't have the time to either. Although I haven't done much dictation on this book, I can feel some slight improvement at listening Swedish.

This week, I started reading Alkemisten by Paulo Coelho. I find more unknown words in this book, as it's set in a different time and geography. But the text flows on beautifully, I just can't put it down.

I use a pencil to underline new words. Look them up when I feel like to. On top of this, when I finish a page, I'd try to summarize the plot in one or two sentences in Swedish. And I'm happily surprised to see I can actually output some coherent Swedish.

Comparing Arrays by Value in JavaScript

I didn't know I didn't know the answer when my friend showed me a simple piece of JavaScript code and asked me what would happen.

1// {1}
2const a = [1, 2]
3const b = [1, 2]
4a == b // what will happen next? 🕶

He said this caused a bug in a project he was working on and it took him hours to debug. Since I knew arrays in JavaScript are objects. And objects are only equal when they refer to the same thing in memory. If you do it as shown in ex. {2}, the result will certainly be true, because x and y indeed refer to the same thing.

1// {2}
2const x = [1, 2]
3const y = x
4x == y // will certainly be true

In ex. {1}, a and b are defined differently. And I felt very clever when I correctly said the code on line 🕶 will produce a false. But —

“If we compare a.valueOf() == b.valueOf(), the result will surely be true!”

— And I was wrong. This would still give you a false!

But my guess was not without a reason.

Take the code below for an example. k1 and k2 are objects. They are not directly comparable. But you can compare their values using valueOf() method. And they are equal.

1const k1 = new Object('wrapping a string literal with an object')
2const k2 = new Object('wrapping a string literal with an object')
3
4k1 == k2 // false; because you can't compare objects to objects
5k1.valueOf() == k2.valueOf() // true; because the values of k1 and k2 are both strings

It came as surprise to me when it turned out arrays, as objects, do not behave like string objects.

The valueOf() method of an array will return an array, which is, again, at the same time an object. Now we are back to this: “you can't compare objects to objects”.

1const m1 = new Object([1, 2, 3])
2
3m1 // [ 1, 2, 3 ]
4m1 instanceof Array //true
5m1 instanceof Object // true
6m1.valueOf() instanceof Array //true
7m1.valueOf() instanceof Object // true

Then I wrote a method that checks if two arrays are equal in value. This method checks recursively the equality in value of nested arrays.

 1// Definition
 2Array.prototype.equalsInValue =  function (that) {
 3  if (! this && that) {
 4    return false
 5  } else if (this.length !== that.length) {
 6    return false
 7  }
 8
 9  for (let i=0;i<this.length;i++) {
10    if (this[i] instanceof Array && that[i] instanceof Array) {
11      if (!this[i].equalsInValue(that[i])) {
12        return false
13      }
14      continue
15    } 
16    if (this[i] !== that[i]) {
17      return false
18    }
19  }
20
21  return true
22}
23
24// Test
25const x = [1, 2, [[3], [4, [5, 6], ['hello', 'world'] ]]]
26const y = [1, 2, [[3], [4, [5, 6], ['hello', 'world'] ]]]
27console.log('comparing x, y: ', x.equalsInValue(y))
28// comparing x, y:  true

I ignored the case where objects are nested inside arrays though. Before I began to take into account objects, I found out someone on StackOverflow had already done that many years ago.


On the other hand, comparing lists in Python is rather uninteresting:

 1x = [1, 2, [3], [4, [5, 6]]]
 2y = [1, 2, [3], [4, [5, 6]]]
 3print(x==y) # True
 4
 5x1 = [1, 2, [3], [4, [5, 6], {'hello': 'world'}]]
 6y1 = [1, 2, [3], [4, [5, 6], {'hello': 'world'}]]
 7print(x1==y1) # True
 8
 9class MyObj:
10    def __init__(self, val):
11        self.val = val
12    def valueOf(self):
13        return self.val
14
15j = MyObj([1, 2, 3])
16k = MyObj([1, 2, 3])
17print(j == k) # False
18print(j.valueOf() == k.valueOf()) # True