React Native from a Mobile Developer Perspective

I spend a few days writing my first Android and iOS app with React Native (I’m an experienced mobile developer). I didn’t want to write a demo app that does just the basics, and I wanted to explore the things that could be problematic with React Native:

  • The app must feel like any native app: smooth and looks like native on both iOS and Android. For example: a toolbar (with text and icon buttons), respecting material design margins, transition between screens, etc.
  • Easy way to access local storage (sqlite for instance).
  • Handle push notifications.
  • Make sure the tools are good: IDE, checkstyle, linter, debugger, etc.
  • Generated app size.

The app I wrote is totally useless (it’s a mix of navigable screens via tabs and stacks, with lists, buttons, icons, images, cards, etc).

 

The awesome

React components. React components are really powerful, especially when you compare this with the traditional way of grouping views in Android (aka. Fragments). Really nice to separate purely visual components and components that handle the logic (aka dumb and smart components). Great to compose bigger components from atomic components. React ecosystem. Especially Redux. I’m not familiar with JS and the setup was not easy. Redux’s store maintains the app state and it’s interesting for mobile because it can also be used for navigation. If your store is well structured, you won’t have to think about things like activities going to the background or device rotations. There are plenty of redux middlewares that allow you to do complex things by just adding a few lines of code. Hot reloading. It works and it’s fast. Save your source file and ~200ms second later you can see the change on your emulator / device.

 

The good

Modern Javascript. I remember when I tried to start a react native app ~2 years ago, I was fighting with JS to write a simple class or export a function. It’s solved in ES6, and the syntax is clean. It’s not the only thing coming from ES6 and ES7, but this simple thing made my life much easier. Flexbox. I like it, never had any issue to create something I wanted, I was a bit confused with alignItems but that’s the kind of thing you learn by using the tools. Type checking. I discovered flow after reading some examples. It allows you to type check your JS code. Coming from Java/Kotlin/ObjC/Swift development, this is pretty nice to have. (Typescript is another alternative and seems pretty easy to setup). NativeBase. It’s a set of native components (built on top of the official components), that allow to write themeable cross platform apps. Some nice utilities as well (includes thousands of icons for example). I used the Card, Button and Checkbox components, they look like native can be mixed with “standard” components. This is why I can say my app looks like a native app. That wouldn’t be the case if I only used the core components. Adding new dependencies. It’s actually easier than in an Android project. Example to add the react-native-fs dependency:

 

# Add the JS dependency: 
$ npm install react-native-fs --save 

# Link the native module in the iOS and Android projects: 
$ react-native link react-native-fs

 

Expo.io. You have an iOS device, but you don’t have a Mac or you don’t want to install XCode? Expo allows you to write basic React Native code (ie. without external native modules). A bunch of utilities are bundled with the library so you shouldn’t have to install external native modules for a basic app. You can even do some basic experiments from your browser, thanks to Expo Snack. Local Storage. There is a core component called AsyncStorage, it’s a key-value storage system. I think it’s enough for most apps, and if you really need to sort, filter, search and do other operations in the data in your app, there is also an external library that wraps sqlite using the same Javascript API for iOS and Android. Apk size. Final apk size of the app is 9Mb, which is not small for a simple app with almost no assets, but not huge. Definitely in the “normal” zone. Most of it comes from ./apk/lib/x86 and  ./apk/lib/armeabi-v7a (native libraries including the Javascript interpreter libjsc.so, the stl, Fresco, some RN jni code). Developer tools. It’s a good suprise, but you can use a lot of the Chrome dev tools plus the react-devtools, but also redux-devtools to track and edit your app state. A whole new world to explore. I didn’t have time to explore, but I read some articles about some super exciting tools and libraries like: react-apollo, CodePush, React Native for Desktop (OS X, Windows)

 

The bad

Navigation. It’s a super easy task in native Android and iOS, developers don’t even have to think about it (unless you have to implement deeplinks). But in React Native, it’s not that easy. And to make it even more complex, they have an history of writing the same kind of library 3 times and give them similar names. After reading recent blog posts about it, it seems there are two viable alternatives: React Navigation (it’s only ~6 months old) and Wix React Native Navigation. I wrote my app with React Navigation, things were going pretty well, until at some point I just wanted to replace the top of my StackNavigator by a new screen instead of poping/pushing a new screen. After some dirty route hacking, I was able to replace the top screen, but I also lost my transition animation. Documentation. The official documentation is pretty shallow (example there is no explanation about linking to a local image, but if you read the unit tests, you can actually find some examples). Community documentation (ie. blog posts from react native devs) is also hard to follow. Because things are changing very fast, you often read an outdated blog post that could actually derail your understanding of a certain topic. Things are moving fast, if you wrote a React Native app 1 year ago, you probably had to maintain and upgrade it to recent a recent React Native version. I don’t have any experience on this, but I guess it’s not always trivial and it’s probably time consuming. Push notifications. The core API allows to handle push notifications but only for iOS (see PushNotificationIOS). I actually found a library react-native-push-notification that implements it for Android and wrap the core PushNotificationIOS, I’m not sure why this is not part of the core modules. Steep learning curve. It’s definitely not easy, I’m just starting (I had some JS experiences before). I was pretty discouraged when I started because I couldn’t just write my app, I was just struggling with some stupid problems (see notes below).

 

The ugly

Access filesystem. Download a file and read it from the app? Put data into a your assets/ folder and read it from the app? It’s not standard, but there are workarounds (like storing your data in .json file and package/require it with your React app or using an external library). That’s actually why I ejected my app (and I then noticed there are some methods in Expo to access the filesystem). To me it’s a big missing piece from core react native. Threading. There are only 2 threads: the UI thread (where native layout happens) and the JS thread (where the JS code is executed, it syncs with the UI thread regularly). This can lead to some performance issues if your JS thread is doing heavy work and the UI can’t sync up. You can also write native modules that spawns new threads and do other stuff there, that might be a requirement for things like image manipulation, you probably won’t do it in pure JS anyway.

 

Notes

Ejecting my app. I used a cli utility to bootstrap my app, it’s called create-react-native-app or CRNA. Took me some time to figure out that was an Expo.io app. I was trying to add a native module and my app structure was different from the examples and docs I was reading. I finally stumbled upon that blog post and was pretty happy that I could just run npm run eject and get my native code compilation process back (ie. iOS and Android project structures). IMO, the naming of CRNA is pretty confusing. Accessing local images. I’ve put app’s local data in a JS file, that looks like: data = {title: "My Title", image: "assets/local_image.jpg"} and then I wanted to use that image in one of my component by doing something like:<Image source={uri: this.props.data.image}> – I finally found it was supported by reading this test in react native unit tests. For some reasons, I have to use the Android id (without the extension) and the filename on iOS. This is still an open issue, I guess the next step is to read the Image code. Navigation, screen replacement. I wanted to replace the top screen of my StackNavigator. Pushing / Popping screens is pretty easy to handle, but there is no way to replace the top screen of a StackNavigator without hacking the router. I did so, but I don’t have any transition animation anymore, so this is still an open issue. Maybe my navigation structure is incorrect. This is the kind of thing you learn by experience. Anyway, it’s a pretty standard use case, and I’m not the only one interested by this feature.

 

Tips

  • Use Visual Studio Code with the React Native extension, it’s really great. I also tried DecoIDE but VSC is so much better. I couldn’t stick with DecoIDE (can be great for learning the component parameters).
  • A doubt about a specific component? read the tests.
  • Source of NativeBase kitchen sink app is also useful if you use NativeBase.
  • If you don’t know anything about React and Redux, read the source code of a very simple demo app to understand the flow (which part call which part, where the data is stored and accessed, etc.)
  • Curated list of articles, tools and libraries: Awesome React Native.

 

Learn

 

Conclusions

I was able to implement everything I wanted, the toolset is great, the app is smooth, looks like any Android native app (the app I wrote is cross platform but follows material design specifications). I’m a bit worried about relying on external dependencies for basic things like push notifications and accessing the file system. And I’m really worried about the navigation (I will try other navigation libraries). Someone with almost no knowledge of React and the JS world will probably spend most of his time struggling with the basics and being stuck on some simple problems that could be solved in seconds by using the native sdk. But someone with a good knowledge of React Native can write a semi-cross-platform app that looks like a purely native app in a short amount of time (compared to write 2 pure native apps), especially if that app can be built on atomic components. I’m really pissed off by the Android Activity + Fragment lifecycle, so having another way of building an app that removes this pain is nice to see (I’m aware of some alternatives Scoop, Flow+Mortar, but never tried them). If I had to start an app from scratch targeting iOS and Android, I’d definitely start by doing a react native experiment and try to implement what could be the biggest pain point.

 

Next

I’d like to try Weex (a Vue.js equivalent for mobile apps) and I’d also like to try wrapping a native library (for iOS and Android) as a react native module.

 

Git Tip: Delete Remote Tags

Filter and delete local and remote tags. In the following example, I want to delete all tags starting by alpha-:

git tag | grep ^alpha- | xargs git tag -d
git tag | grep ^alpha- | xargs -I % git push origin :refs/tags/%
 

Keeping an eye on some interesting Bitcoin and Ethereum products

Bitcoin

  • OpenBazaar – decentralized eBay.
  • Blockai – proving ownership.
  • BitPesa – cheap remittance, RIP Western Union.
  • Blockstream – sidechains, allow new features on top of the Bitcoin blockchain without changing the protocol.
  • Trezor – hardware wallet, secure your bitcoins.

Ethereum

  • Akasha – decentralized social network.
  • Slock.it – IoT and decentralization, e.g. rent your unused WiFi bandwidth, smart locks, etc. Previously: TheDAO.
  • uPort – Identity and reputation services.
  • Swarm – serverless hosting.

I sincerely hope to add a Decred section for the next update of this post.

Note: this is no investor advice, the topics and the solutions they propose looks very interesting to me, but I’ve no idea if there is a market for it and how they manage their companies. I was super excited about bonafide.io (identity and reputation services) which ended operations ~a year ago and TheDAO which resulted in an epic Ethereum fail (hard fork).

 

Shell tip: Generate Numbered Images

Generate images 00.jpg, 01.jpg, etc. via imagemagick using 8 threads:

seq -f "%02g" 0 99 | xargs -P 8 -I % convert -background white -fill blue -gravity center -size 600x400 -pointsize 300 label:% %.jpg

Sample images:
99 42  00

 

Android Material Styling

Very useful card, thanks moshdev.

android material styling card

 

Android Dev Tip: Hide that Annoying Java Icon

When you run ./gradlew in your Term, it sometimes spawns a few java utilities, like the linter. On OS X, these java utilities greet you with an annoying Java icon that appears and never disappears in your Dock, plus you lose focus on your Term.

shot

To hide this icon forever (for all java apps started from your shell), add this line to your ~/.bashrc or ~/.zshrc:

export JAVA_TOOL_OPTIONS="-Dapple.awt.UIElement=true"
 

Shell Tip: Search and Replace in line

Replace the word “Cat” by “Pony” in all the files of the current directory and subdirectories:

a=Cat; grep -lr $a . | xargs perl -pi -e s/$a/Pony/g
 

List MAC addresses on your local network

Just in case you’re stuck in an hotel with a $40/day wifi access. The usual solution is to spoof a MAC address (ie. use one from someone already connected). But how to list them?

On OS X, the easiest is to use the arp command:

$ arp -an | grep -v incomplete

If you want to make sure the device is currently connected, use nmap (replace 10.0.*.* by your subnet):

$ nmap -sP 10.0.*.*

And then, you just have to spoof one of the MAC address:

$ sudo ifconfig en0 ether CA:FE:CA:FE:CA:FE
 

Copy/Paste to your Android device or emulator

I’ve been using the stock Android emulator these days. And the lack of copy/paste is annoying. There is a way to input text to any adb connect devices using adb shell input text, so I added a couple of functions to my .zshrc (works with bash too).

ai () { echo "$@" | sed "s/%/%%/g" | sed "s/ /\%\s/g" | xargs adb shell input text }
alias aip='pbpaste -Prefer txt | sed "s/%/%%/g" | sed "s/ /\%\s/g" | xargs adb shell input text'

Usage, to input text (including spaces) to your device:

$ ai test is cool

Usage, to paste the text in your clipboard to your device:

$ aip

Note: works on OS X, replace pbpaste -Prefer txt by the linux / windows equivalent.

 

Favorite Chrome Extensions

  • StayFocusd – to limit my time spend on Hacker News and Reddit to a maximum of 10 minutes / day.
  • PocketSend to Kindle – to save articles to read them later (I’ll drop Pocket soon, I noticed I’m reading much more stuff on my Kindle).
  • Disconnect – to stay out of sight from (some) analytics and other trackers.
  • Pushbullet – to write SMS from my computer and share stuff between my Android devices and my computer.
  • uBlock Origin – because some sites are cluttered with ads, good players whitelisted.
  • HTTPS everywhere – use SSL when available.
  • Stylish (to apply a Dark theme on my favorite sites: GitHub for example – reduce eye strain).
  • Tampermonkey – with a bunch of home-made scripts hacks.

 

 

Procmail Tip: MS Word Attachments Black Hole

Your spam/ mailbox is full of .doc files like mine? Your contacts never send you .doc or .rtf files? Then add this rule to your Procmail config!

# Word attachments black hole
:0
* ^Content.Type:.*multipart.*
* B ?? ^Content.Type:.*name=.*\.(doc|rtf).*
/dev/null
 

Pseudo Random Number Generator and Bitcoin

I’ve stumbled upon two implementations of bitcoin libraries that generate new bitcoin addresses based on a secret. To generate that secret, the first one is using time as seed to srand(), the second one is using its own random generator which is not cryptographically secure (it’s open source, so quite easy to reverse engineer it and get the full set of generated secrets). I contacted the authors of these libraries in the hope they’ll fix that. An attacker could easily find some (or all) valid private keys these libraries generated.

Reminder: on your computer time is discrete. Using srand(time(0)) is very common, and if you’re using it for your new procedural generated game, it’s good enough, but when it comes to generate bitcoin addresses: be careful. Example:

srand(time(0));
int secret = rand();
char *address = bitcoin_address(secret);

In that case, time(0) is very discrete since it only has a one second resolution. Say that code has been published on January 1st, 2011. You can list all private keys generated by that code until today:

int january_1_2011 = 1293840000;
for (int i = january_1_2011; i < time(0); i++) {
  srand(i);
  int secret = rand();
  char *address = bitcoin_address(secret);
}

That’s only 146 927 544 keys (number of seconds from January 1st, 2011 to today), millions of bitcoin private keys can be easily tested and money transferred to the attacker.

So if you ever have to use a random function when you work on a Bitcoin project:

  • Make sure you understand PRNGs.
  • Never use default language implementation of random – they’re never cryptographically secure.
  • Never trust the OS.
  • Make sure to seed with high resolution data (and search for “Entropy Gathering”) if you ever have to seed yourself.
 

Replaced ack by ag

I’m using ack 100 times a day, it’s written in Perl and a bit slow when grepping a big directory. I recently switched to ag (aka the_silver_searcher). It’s much faster and ignores file patterns from your .gitignore. I see no reason to use ack anymore so:

$ brew install the_silver_searcher
$ brew remove ack
$ echo "alias ack=ag" >> ~/.zshrc # my muscle memory doesn't want to switch
 

Use Genetic Programming To Generate File Converters

Introduction

Here is an old article I wrote in January 2009. Since then, I received some emails and a lot of 404 errors, so I decided to repost it on this “new” blog. You can find the code here on github.

Genetic algorithm, another metaheuristic inspired by evolution of species. You can read the description of the algorithm on the genetic algorithm article on Wikipedia.

I applied the algorithm to a concrete problem: help lazy programmers and non-programmers to write file converters. I had to write file converters to unify all (more or less) formatted input files into one kind of CSV file. Each of these converters is made using the right combination of filtering / regexp matching / line splitting.

Description

So I wrote a program based on genetic algorithm where an individual is composed by 3 “genes”:

  • a list of filters (remove consecutive spaces, replace tabs by spaces, …)
  • a list of basics regexp to extract formatted basic blocks(int, float, date, line separator, …)
  • a list of cleaning functions (remove empty cell, merge cells, …)

The fitness of an individual is calculated using a sample file to parse that goes through the genes (filters / regexp / cleaning functions). The result of this process is a CSV file that can be compared to the expected sample result (that I wrote manually). The comparison uses the SequenceMatcher of the difflib Python stantard module, it returns the fitness: a float. A fitness close to 1.0 means the results is close to the expected CSV format. When the fitness is exactly 1.0, that means the converter works perfectly for the sample.

Here is a sample file I wanted to convert:

08/12        Hello world 06/12
Paris 121231231         - 22,29
08/12   Something something ... 04/12
1111 1111 1111 1111         - 14,35
08/12   something else
        - 12,96
26/11   Vir AAAAA
AAAAAA 2008     264,51

into this csv file:

"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

The program prints for each generation the 5 bests individual (I’m using elitism, so the best individual is always kept from a generation to the next one). A sample run:

$ python ga.py tests/sample1.txt tests/sample1.expected result1.pickled
Generation: 0 (mutation rate=10)
0.53772
0.42507
0.30406
0.28598
0.26389
Generation: 1 (mutation rate=10)
0.53772
0.42507
0.32684
0.30406
0.26799

...

Generation: 271 (mutation rate=15)
1.0
0.96025
0.95107
0.91779
0.87886
"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

filters: str_remove_consecutive_spaces, str_remove_somespaces, str_strip, str_remove_consecutive_spaces
regex: ([0-9]{2}/[0-9]{2})(.+?)(
)(.+?)(-?[0-9]+[.,]+[0-9]+)
cleaners: clean_strip, _in, _in, _in

Conclusion

The good:

  • It’s fun to watch your program evolve 😉
  • You are lazy and don’t want to write _many_ of this kind of file converters. This was used in a real life problem, with more than 200 different input file formats.
  • With a good interface and if the basic functions and genes size are well-defined, a non-programmer can create his own parser.

The bad:

  • The resulted parsers are not optimal

The ugly:

  • Of course it’s quite easy to write such genes by hand
  • It may never converge to 1.0 and generated parsers of fitness != 1.0 are useless (this may not be the case for other kind of GA applications)
  • You need many well-chosen primitives to cover a wide set of solutions

What next? Write a simple Web interface to help people generate their own converters. Add new construction blocks. Use the same idea to automatically plot any kind of formatted data.

 

Git tip: delete local branches already merged in master

To delete only issue/ and feature/ branches:

$ git branch --merged master | grep -E "issue/|feature/" | xargs git branch -d
 

Git tip: pre-commit hook – avoid commit FIXMEs

In my code, I sometimes add some FIXME tag (just the FIXME string in a comment or in a debug print). And before staging them in git, I review my diff to check for them. And rarely I miss one FIXME line or debug print, stage it and then commit it. To avoid that, I just wrote a quick pre-commit hook that greps the regexp "[Ff][Ii][Xx][Mm][Ee]" in staged diff using the command git diff --cached -G "[Ff][Ii][Xx][Mm][Ee]".

Here is the full script:

#!/bin/sh
exec 1>&2
FORBIDDEN_RE="[Ff][Ii][Xx][Mm][Ee]"
if [ $(git diff --cached -G "$FORBIDDEN_RE"|wc -l) != 0 ]; then
    git --no-pager diff --cached -G "$FORBIDDEN_RE"
    echo
    echo "ERROR: You're trying to commit a line containing the $FORBIDDEN_RE re"
    exit 1
fi

Put that in the file .git/hooks/pre-commit and next time you’re trying to commit a file containing “FIXME”, it will abort and print you the involved diff.

Note that you can ignore the pre-commit hook with the following command:

$ git commit --no-verify
 

Self Hosted Encrypted Backups

Note: It’s not really an alternative to Dropbox since you can’t share your files with others. But personally I’m also using Dropbox to backup some of my important data (encrypted data like Bitcoin wallets or KeePass / 1Password file).

I was looking to setup a private incrementing encrypted backup, like rsync but with encryption. And I found duplicity. So I setup my cron to run this command every night:

$ duplicity --ssh-options="-oIdentityFile=~/.ssh/max.example.priv" 
  /home/max/wallets/ scp://max@example.com//home/max/backups/wallets/

Install it on OS X:

$ brew install duplicity
$ pip install paramiko

On Ubuntu

$ sudo apt-get install duplicity
 

System Wide gitignore

I now added my specific temporary folder to my system wide gitignore. Small impact for me, a huge impact for multi-project people I work with 😉

$ sudo git config --system core.excludesfile /etc/gitignore
$ sudo sh -c "(echo '*~'; echo ".DS_Store"; echo "tmp-max/") > /etc/gitignore"
 

You should buy some bitcoins now (july, 8 2013)

Since now, I bought bitcoins for those reasons:

  • First to learn. I always thought the easiest way to learn about something is to experiment with it. And with my first bitcoins (bought at $2 and then at $5.5 each) I learned the basics: where to buy bitcoins, what is a transaction, what is a confirmation, what is mining, what is the bitcoin economy. I tried 5 bitcoin clients: web, mobile, native. I Wrote some scripts and plugins, I installed woocommerce + bitcoin plugins to test the ease of opening a bitcoin eshop. I read bitcointalk.org to learn more about projects, IPO, economy.

  • A dream: my life without being a bank customer. Because to live in any developed country, you must be a bank customer. I’m 99.99% sure that dream will never come true, but at least if I could avoid Paypal, VISA, Mastercard that would be great.

  • I want bitcoin to be the future of money. if you want that, you should start using bitcoin and contribute to the economy by selling and buying things. I was pleased:

    • to pay for Reddit Gold with BTC
    • to buy my last Humble Bundles with BTC
    • to sell and buy stuff on http://www.bitmit.net
  • To spread the word: give small amounts to your friends and family. It works, my friends know about bitcoins and some of them own bitcoins.

After that, I started to work for bitcoins, I’m a software developer working as freelance. I found a couple of contracts paid in bitcoins.

And I sold some because:

  • When you’re paid in bitcoins, you still need to pay the bills and taxes in $/€/¥ depending where you live.
  • I needed some cash to travel (it’s hard to find hotels and restaurants that accept bitcoins in China)

  • I did arbitrage, that implies to buy and sell bitcoins. I earned some BTC by doing this and it helps exchanges to stay aligned.

If I had cash, I would buy some today as an investment. When I write “investment”, that does not mean: “to sell later at a higher price”, that means: “to don’t have to buy them later at a higher price”. No one knows if it the good moment to buy, but the price seems low compared to the growing economy, the number of future bitcoins startups ready to launch and the very fragile banking system the world has.

 

Stay Away From Bitcoin Arbitrage If You’ve Got A Heart Condition

This must be true for most financial activities. But since I’m
receiving something like 5 emails per day from random people [1] who
wants to run my
bitcoin-arbitrage tool,
most of the time I’m replying with some warnings:

  • Can you trust the exchanges ? The answer is NO, you can’t:

    • Trade engine can be laggy (up to 1 hour lag).

    • APIs are buggy. get-order-book replying with 2 hours delay is
      unacceptable. some API function doesn’t work time to time

    • Bad “cloudflare” config sometimes blocks normal API calls (Yes,
      I’m looking at you bitstamp)

    • The site closes but a part of API is still working (Yes, i’m
      looking at you bitcoin24)

    • And the worst thing: they can close at every moment and block your
      money (1 hour to infinity). History prove this one, see what
      happened to Bitcoinica, Bitfloor, Bitcoin24,
      Bitcoin-Central. Who’s next ?

  • Can you trust tools ? Of course NO. If you can’t read code (blind,
    not a developer or closed source), don’t use the tool. A malicious
    dev can steal your money so easily.

  • To trade you need money, fiat AND bitcoin. If you don’t have
    bitcoins, are you ready to buy some ? Yes, risks everywhere !

  • Moving fiat is so long… SEPA transfers ? sure let me wait a week
    (I’m wondering why it’s so slow, do banks have computers ?). That
    means you’ll need A BUNCH of money (fiat AND bitcoin) in every
    exchanges you’re trading on. Then balance them time to time when
    they drift. And that opens a big risk if one exchange closes and
    blocks your money.

So yes, Bitcoin arbitrage seems easy and very lucrative, but it’s very
risky. Not because of arbitrage principle itself, but mainly because
you can’t trust exchanges.

[1] random people includes: developers (who wants to rewrite the tool
in Ruby, Java, C, Javascript, Python 2.x), students (finance, math),
home trader (that one is scary), unknown (“hey, i stumbled upon your
program, I’ll give you $500 to make the setup on my computer”).

 

Redis ZSET Underlying Datastructure

Sorted Sets: ZSET

Redis ZSETs are a very good to store ordered data like leaderboards:

  • You need to get the current score for an userid (every SQL or NOSQL
    can do that efficiently)
  • You need to get the current rank for an userid
  • You need to get a list of pairs userid/score sorted by score

Datastructure

In the Redis documentation, we can read complexity is O(lg(n)) to ZADD / ZRANK / ZREM and O(1) for ZSCORE. How are they implemented ? O(lg(n)) you said… hmmm smells like a tree or binary search. ZSCORE (a kind of search) in constant time… hmmm smells like a hashtable. So how is it implemented ? a mix of hashtable and tree ? No, but that’s close, it’s a mix of hashtable and Skip List. Skip list are an alternative to balanced binary tree.

You should read the original Skip List paper.

From the redis documentation:

ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.

The elements are added to an hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this “view”).

So, how to perform a ZRANGEBYSCORE in linear time ?

  1. search the min element. O(lg(n)) complexity (with n=|set|)
  2. start from min and follow links to the next element until you reach max. O(m) complexity (with m elements returned)

Also, there is a modification from the original skip list implementation, level 1 list is doubly linked, so it gives you: ZREVRANGE, yeah !

 

Algorithm Complexity

I started to code some random problems from Project Euler. To have an extra hint of which kind of algorithm I’m looking for, I made the following table.

Read it like: “Assuming a computer can do 10 000 000 operations/sec, with a O(n^2) algorithm, you can solve a n ~ 3000 under a second”

Complexity      |   n for 1 second  |   n for 1 minute
------------------------------------------------------
O(1)            |   inf             |   inf
O(lg(n))        |   huge            |   2^(10^7)
O(sqrt(n))      |   10^14           |   36*10^16
O(n)            |   10 000 000      |   600 000 000
O(n*lg(n))      |   526 172         |   24 446 750
O(n*sqrt(n))    |   46 415          |   711 378
O(n^2)          |   3162            |   24 494
O(2^n)          |   23              |   29
O(n!)           |   10              |   12

Project Euler problems should be solved under 1 minute (even in Python, most problems I solved has been < 2 secs), so if the input N is ~10 000 000, you should look for a O(n*lg(n)) solution or better.

Also if you’re developping Python code, you should have a look at these Python Time Complexity Tables. I think other language libraries use the same underlying datastructures and algorithms.

 

List redis keys, filter some of them, then hget on this filtered keys

$ echo "keys *" | redis-cli | grep user 
                | xargs -I % sh -c "echo hget % name | redis-cli"
 

Bitcoin Arbitrage

I updated my bitcoin arbitrage project: https://github.com/maxme/bitcoin-arbitrage

More modular and now include trading bots if you want to automate buy and sell orders on some exchanges.

 

Bitcoin Arbitrage Opportunity Watcher

I released a quick hack to watch for bitcoin arbitrage opportunities. Code and documentation are on github: https://github.com/maxme/bitcoin-arbitrage

I made some bitcoins with it, pushing coins from mtgox to bitcoin central and back. If you are crazy enough to plug a API-trading tool, you should be one of the few bitcoin automated arbitrage trader.