Geek asks and answers

Search for substring asynchrony. Recursion? Mixing?

I really like node.js with redis, but I can't beat asynchrony. Again I have a simple task in a traditional database and language. My question is more related to the execution of the control flow and logic in the asynchronous selection of the database than the optimal approach to solving problems or not.

Here's what I'm trying to do: I have redis keys made up of words, let's just say carand card. Now, given the input string, I want to know what is the longest substring that matches the key in redis. I only need to check the substrings starting at position 0 of this string, so the complexity is low.

Example: cardinalhas a key in it card, as well car, but cardlonger. Capedoes not match any of the keys.

My approach: start with the whole line and check if it matches the key. If so, return this key. Otherwise, repeat the same process with a line minus the last character.

How can I complete this task? Various approaches are welcome.

I am a little versed in the library asyncand it seems to me that is waterfallbest suited for what I am doing. However, it seems that I need to enter all the functions from string.length, string.length-1, etc. To the last single character. What I'm looking for is a good replacement for a for loop with a break.

Below I test with the input, I assume that it is always 3 characters or more (because it is already ugly and more nesting seems pointless for testing). It works, cardeleads to cardand care→ car. Stupidity gives no match.

var http = require("http");
var redis = require("redis");

http.createServer(function(request, response) {
    client = redis.createClient();
    word = "carde";
    client.keys(word, function(err, reply) {
        if(err) { response.end(err); client.end(); }
        else {
          if(reply.length > 0) {
            response.end(word);
            client.end();
          }
          else {
            client.keys(word.slice(0,-1), function(err, reply) {
                if(err) { response.end(err); client.end(); }
                else {
                  if(reply.length > 0) {
                    response.end(word.slice(0, -1));
                    client.end();
                  }
                  else {
                    client.keys(word.slice(0, -2), function(err,reply) {
                        if(err) { response.end(err); client.end(); }
                        else {
                          if(reply.length > 0) {
                            response.end(word.slice(0, -2));
                            client.end();
                          }
                          else {
                            response.end("no match");
                          }
                        }
                      });
                  }
                }
              });
          }
        }
    });
  }).listen(8000);

I also tried recursion, and this might be the best method. (Thanks to Timonthy Strimple for fixing the bug).

http.createServer(function(request, response) {
    client = redis.createClient();
    recursiveKeys("cardinalsin", client, response);
  }).listen(8000);

function recursiveKeys(word, client, response) {
  if (word.length == 0) {
    response.write("0");
    response.end();
    client.end();
  }
  else {
    client.keys(word, function(err, reply) {
        if(err) {
          response.write("0");
          response.end();
          client.end();
        }
        else {
          if(reply.length > 0) {
            response.write(word);
            response.end();
            client.end();
          }
          else {
            return recursiveKeys(word.slice(0,-1), client, response);
          }
        }
      });
  }
}
+3
source share
1 answer

I agree that a recursive solution is probably the best. I approached this problem before studying your code (so as not to affect the experiment) and came up with a very similar solution. Find the word withhttp://localhost:3000/?word=cardinal

var http  = require('http');
var redis = require('redis');
var url   = require('url');

var findWord = function(needle, client, callback) {
  if (needle.length <= 0) { return callback("Word not found") }

  client.keys(needle, function(err, reply) {
    if (err) { callback("Word not found"); }
    else {
      if (reply.length > 0) {
        callback(needle);
      } else {
        findWord(needle.slice(0, -1), client, callback);
      }
    }
  });
};

var server = http.createServer(function(request, response) {
  var query  = url.parse(request.url, true).query;
  var word   = query.word || "";
  var client = redis.createClient();

  findWord(word, client, function(found) {
    client.end();
    response.writeHead(200, {"Content-Type": "text/plain"});
    response.end(found);
  });
});
server.listen(3000);
+4
source

More articles:


All Articles