Filtering FASTQ file based on read names from other file (how to increase performance) Python I have some code here that basically takes in a list of IDs (sequencing read names) using STDIN, and then filters fin (a gzipped FASTQ file) to just those reads with a read name which matches one of the IDs, and then writes the name and sequence to fout (a gzipped FASTA file). Fairly standard data processing problem in bioinformatics.
The code below can run through about 100k/sec lines of fin, however fin is about 500M lines, so it still takes over an hour.
Can this be sped up significantly? I'm hoping for a 10x or better improvement in performance. I may be taking a performance hit running line.decode('utf-8'), however it's necessary for matching since gzip files are read as bytestring. I'm willing to drop down and rewrite this in C if this will substantially increase speed.
import sys
import gzip
import re

id_array = []
for line in sys.stdin:
    id_array.append(line.rstrip())

ids = set(id_array)

with gzip.open(sys.argv[1], "r") as fin:
    with gzip.open(sys.argv[2], "w") as fout:

        take_next_line = False
        for line in fin.readlines():
            seq_search = re.search('[@+]([^\s]+)', line.decode('utf-8'))

            if take_next_line:
                fout.write(line)
                take_next_line = False

            elif seq_search and seq_search.group(1) in ids:
                take_next_line = True
                fout.write('>' + line[1:])

Do not reinvent the wheel. There are bioinformatics tools that accomplish this task.
To extract reads from fastq files by IDs, use seqtk subseq.

Extract sequences with names in file name.lst, one sequence name per line:
seqtk subseq in.fq name.lst > out.fq

It works with fasta files as well.
Use conda install seqtk or conda create --name seqtk seqtk to install the seqtk package, which has other useful functionalities as well, and is very fast.
Alternatively, use BBMap filterbyname.sh, see docs:

By default, "filterbyname" discards reads with names in your name list, and keeps the rest. To include them and discard the others, do this:
filterbyname.sh in=003.fastq out=filter003.fq names=names003.txt include=t

SEE ALSO:
Extracting specific sequences from FASTQ using Seqtk
How To Extracting Fastq Sequence For Given Fastq Ids And Fastq File
How To Extract A Subset Of Reads In Fastq Using An Id List?


Copy autodiscovery results from list to an array I copy addresses from the endpoints to an array that should only hold the endpoint addresses. This works but it seems so old school :/

Can I make this faster, better, more sexy (LINQ)?

public static EndpointAddress[] Find()
{
    EndpointAddress[] endpointAddresses = null;
    var discoveryClient = new DiscoveryClient(new UdpDiscoveryEndpoint());
    var findResponse = discoveryClient.Find(
        new FindCriteria(
            typeof(ICommunicationService)));

    if(findResponse != null)
    {
        if(findResponse.Endpoints.Count > 0)
        {
            endpointAddresses = new EndpointAddress[findResponse.Endpoints.Count];

            for (int i = 0; i <= findResponse.Endpoints.Count; i++)
            {
                endpointAddresses[i] = findResponse.Endpoints[i].Address;
            }
        }
    }

    return endpointAddresses ?? new EndpointAddress[0];
}

You certainly can! You're currently coding using the "arrow pattern" it's often nicer to return early rather than keep indenting further and further as you nest conditionals.

if (findResponse == null)
{
     return new EndpointAddress[0];
}

Now let's make the rest of the method shorter:

public static EndpointAddress[] Find()
{
    var discoveryClient = new DiscoveryClient(new UdpDiscoveryEndpoint());
    var findResponse = discoveryClient.Find(
        new FindCriteria(
            typeof(ICommunicationService)));

    if(findResponse == null)
    {
        return new EndpointAddress[0];
    }
    return findResponse.Endpoints.Select(endpoint => endpoint.Address).ToArray();
}

But, we can go further. You should prefer returning interfaces rather than concrete representations. Do you need indexed access to the EndpointAddresses? I doubt it, return IEnumerable<EndpointAddress> instead:

public static IEnumerable<EndpointAddress> Find()
{
    var discoveryClient = new DiscoveryClient(new UdpDiscoveryEndpoint());
    var findResponse = discoveryClient.Find(
        new FindCriteria(
            typeof(ICommunicationService)));

    if(findResponse == null)
    {
        return Enumerable.Empty<EndpointAddress>();
    }
    return findResponse.Endpoints.Select(endpoint => endpoint.Address);
}

You could also inject the DiscoveryClient into the classes constructor but as it is a static method and I don't know what the rest of the class looks like, I'll leave that point for now.


jQueryTools plugin custom effect for caching ctabs This is a custom effect for jQuery tools that enable caching for ajaxed tabs.
Please advice on anything that I can improve. Note that I'm not sure where to put the loading indicator, so, at least have a look at that.

$.tools.tabs.addEffect("ajax_cache", function(tabIndex, done) {
    //check if content already loaded
    //if yes, display it, and hide the rest
    //if no, send ajax request

    var panes_cont = this.getPanes().eq(0);
    var dest_pane = panes_cont.find("#tabindex_"+tabIndex);
    if(dest_pane.length > 0){
        panes_cont.children().hide();
        dest_pane.show();
    } else {
        panes_cont.children().hide();
        panes_cont.append("<img id='tab_loading' src='/graphics/loading.gif' />");

        var new_pane = $('<div>').attr('id', 'tabindex_'+tabIndex).load(this.getTabs().eq(tabIndex).attr("href"),
        function(){
            panes_cont.find("#tab_loading").remove();
            panes_cont.append(new_pane.show());
        });

    }

    done.call();
});

From a once over :

Whether the content is loaded or not, you call panes_cont.children().hide();, you might as well centralize that 1 call
There is too much going on in the creation of new_pane, it ought to be split up.
lowerCamelCasing is good for you, also write out things. cont keeps reminding me of continue whereas you probably mean content
I prefer the line of comment on top of the function
There is no need to check length > 0, you can simply check for length
As Bill Barry pointed out, caching the loader image is more efficient
Most recent js standards suggest to put strings in single quotes, whichever way you go, you should be consistent for easy reading.

All the above together gives this:

//check if pane already loaded, if so, display it, otherwise send ajax
$.tools.tabs.addEffect("ajax_cache", function(tabIndex, done)
{
  var allPanes    = this.getPanes().eq(0).hide(),
      targetPane  = allPanes.find("#tabindex_"+tabIndex);

  if(targetPane.length)
  {
    targetPane.show();
  }
  else
  {
    var loaderImage = allPanes.append('<img id="tab_loading" src="/graphics/loading.gif"/>'),
        newPane = $('<div>').attr('id', 'tabindex_'+tabIndex),
        URL = this.getTabs().eq(tabIndex).attr('href');

    newPane.load(URL, function(){
      loaderImage.remove();
      allPanes.append(newPane.show());
    });
  }
  done.call();
});


Script to hide Excel rows where certain columns contain 0 I have the following script which works, but takes a lot of time to run on a worksheet with 2000+ rows. Anyone know of a way to speed it up?

The code runs through the workbook and ignores the pages I do not want it to touch. Then, it runs through any pages that I want it to, looks for rows with a zero in column C and Column D and if found hides the row.

Sub HideDoubleZeors()

Dim LR As Long, i As Long
Dim c As Variant

For Each ws In Worksheets
Select Case ws.Name
    Case "Form1", _
            "Form 2", _
            "Form 3"
            'Do nothing on these tabs

    Case Else 'If not one of the above tab names then do this
    With ws.Activate
        LR = ws.Range("B" & Rows.Count).End(xlUp).Row
        For i = 1 To LR
        With ws.Range("B" & i)
        For Each c In Range("B" & i)
            If c.Value <> "All Forms" _
                And c.Value <> "Week One All Forms" _
                And c.Offset(0, 1).Value = 0 _
                And c.Offset(0, 1).Value <> vbNullString _
                And c.Offset(0, 2).Value = 0 _
                And c.Offset(0, 2).Value <> vbNullString _
            Then Rows(c.Row).Hidden = True
            Next c

       End With
      Next i
   End With
   End Select
Next ws
End Sub

The first rule of optimizing Excel when formatting: "TURN OFF SCREEN UPDATING"

 Application.ScreenUpdating = False

These line continuations are just ugly.  They add nothing to the readability or functionality of the subroutine.

    Case "Form1", _
        "Form 2", _
        "Form 3"

I would remove the line continuations

   Case "Form1", "Form 2", "Form 3"

There are only a sew cases where it is advantageous to Select or Activate an Object.  This isn't one of them.  Watch: Excel VBA Introduction Part 5 - Selecting Cells (Range, Cells, Activecell, End, Offset)

With ws.Activate

I guess your original code might have needed this line: With ws.Range("B" & i) but now it's just leftover parts.  Remove it.

I hate the old style where you first find the last row and then use it in a loop or Range.  IMO, there isn't a good reason to do this with a simple loop or Range selection.

LR = ws.Range("B" & Rows.Count).End(xlUp).Row
  For i = 1 To LR

What's next..hmm. For Each Cell in My 1 Cell Range????  Have you watched the formationed Excel VBA Introduction Part 5 - Selecting Cells (Range, Cells, Activecell, End, Offset) yet???

For Each c In Range("B" & i)

Range("B" & i) isn't qualified to the ws.  It is referencing the cells of the ActiveSheet. That's probably why you needed to activate the worksheet.

Often it is necessary to unhide all the cells on the worksheet before you reprocess the worksheet.  It probably doesn't apply to this scenario but I thought that I would mention it.

This statement seems somewhat redundant but I'll let someone else handle it.

If c.Value <> "All Forms" _
    And c.Value <> "Week One All Forms" _
    And c.Offset(0, 1).Value = 0 _
    And c.Offset(0, 1).Value <> vbNullString _
    And c.Offset(0, 2).Value = 0 _
    And c.Offset(0, 2).Value <> vbNullString _

Here is the real problem.  You are hiding each row individually.  The preferred method is to create one large Range (per worksheet) and hide all the cells at once.  The easiest way to do this is to use Application.Union.

Then Rows(c.Row).Hidden = True

The other method collects the range addresses and then creates a range from them.  Although faster, its not worth the extra work to processes a few thousand rows.

Rows(c.Row).Hidden = True works but again its ugly use c.EntireRow.Hidden = True

A better way:

Sub HideDoubleZeors()
    Dim ws As Worksheet
    For Each ws In Worksheets
        Select Case ws.Name
            Case "Form1", "Form 2", "Form 3"
                'Do nothing on these tabs
            Case Else                                 'If not one of the above tab names then do this
                ProcessWorksheet ws
        End Select
    Next
End Sub

Private Sub ProcessWorksheet(ws As Worksheet)
    Application.ScreenUpdating = False
    Dim cell As Variant, MyRows As Range
    With ws
        For Each cell In ws.Range("B1", .Range("B" & .Rows.Count).End(xlUp))
            If cell.Value <> "All Forms" And cell.Value <> "Week One All Forms" _
               And cell.Offset(0, 1).Value = 0 And cell.Offset(0, 1).Value <> vbNullString _
               And cell.Offset(0, 2).Value = 0 And cell.Offset(0, 2).Value <> vbNullString Then
                If MyRows Is Nothing Then
                    Set MyRows = cell
                Else
                    Set MyRows = Union(MyRows, cell)
                End If
            End If
        Next
    End With

    If Not MyRows Is Nothing Then MyRows.EntireRow.Hidden = True
    Application.ScreenUpdating = True
End Sub

Hopefully the OP gets more out of this than just some free code.

Good Luck and don't forget to watch that video!!


Code to find the proper index comparing 3 values for max one I have an algorithm and the idea is to move over an array choosing as index the index of the neighboring cell that has the max value.
I.e.

if array[i + 1][j + 1] has the largest value among the 3 then move there.

I have 2 versions of this, but I think it can be cleaner.

version 1:

int maxI = i + 1;
int maxJ = j + 1;
if(array[i + 1][j] > array[maxI][maxJ]){
    maxI = i + 1;
    maxJ = j;
}
if(array[i][j + 1] > array[maxI][maxJ]){
    maxI = i;
    maxJ = j + 1;
}
i = maxI;
j = maxJ;

version 2:

if(LCS[i + 1][j + 1] > LCS[i][j + 1] && LCS[i + 1][j + 1] > LCS[i + 1][j]){
    i++;
    j++;
}
else{
    if(LCS[i][j + 1] > LCS[i + 1][j]){
        j++;
    }
    else{i++;}
}

Both versions occur in a while loop which I omitted for clarity.
How can these versions become better?

I think it's easier to follow the second version. I've extracted out some helper variables:

    final int b = array[i][j + 1];
    final int c = array[i + 1][j];
    final int d = array[i + 1][j + 1];

    if (d > b && d > c) {
        i = i + 1;
        j = j + 1;
    } else if (b > c) {
        j = j + 1;
    } else {
        i = i + 1;
    }

It seems a little bit readable for me but to be honest I'm not completely satisfied with the result.


Does this unit test cover all edge cases? I want to test a simple controller and I want to know if this unit test covers all cases:

Controller:

@RequestMapping(method = RequestMethod.GET)
public List<Tags> getAllTags(@RequestParam(value = "query", required = false) String query,
        @RequestParam(value = "limit", required = false) Integer limit,
        @RequestParam(value = "start", required = false) Integer start,
        @RequestParam(value = "approved", required = false) Boolean approved,
        @ActiveLanguage Language language,
        @ActiveUser User user) {
    if (limit == null) {
        limit = 10;
    }
    if (start == null) {
        start = 0;
    }
    if (approved == null) {
        approved = true;
    }
    if (query != null) {
        return tagService.findTagsByQuery(user, query, limit, start, language, approved);
    } else {
        return tagService.findTags(user, limit, start, language);
    }
}

Test:

@Test
public void testGetAllTags_query_notnull() throws Exception {
    List<Tags> tagsList = createTagList();

    //Individual parameters
    String query = "test";
    Boolean approved = true;

    Mockito.when(this.tagServiceMock.findTagsByQuery(user, query, limit, start, language, approved)).thenReturn(tagsList);

    List<Tags> t = tagController.getAllTags(query, limit, start, approved, language, user);

    assertSame(tagsList, t);
    assertNotNull(t);
    assertNotNull(tagsList);

    verify(tagServiceMock, times(1)).findTagsByQuery(user, query, limit, start, language, approved);
    verifyNoMoreInteractions(tagServiceMock);

}

@Test
public void testGetAllTags_query_null() throws Exception {
    List<Tags> tagsList = createTagList();

    //Individiual Parameters
    String query = null;
    Boolean approved = true;

    Mockito.when(this.tagServiceMock.findTags(user, limit, start, language)).thenReturn(tagsList);

    List<Tags> t = tagController.getAllTags(query, limit, start, approved, language, user);
    assertEquals(tagsList, t);
    assertNotNull(t);
    assertNotNull(tagsList);

    verify(tagServiceMock, times(1)).findTags(user, limit, start, language);
    verifyNoMoreInteractions(tagServiceMock);

}

Is there anything left that is not covered by this unit test?

As far as I can see the
@RequestParam
annotation can have a defaultValue parameter - once that's used the
method becomes a bit simpler:

@RequestMapping(method = RequestMethod.GET)
public List<Tags> getAllTags(@RequestParam(value = "query", required = false) String query,
        @RequestParam(value = "limit", required = false, defaultValue = "10") int limit,
        @RequestParam(value = "start", required = false, defaultValue = "0") int start,
        @RequestParam(value = "approved", required = false, defaultValue = "true") boolean approved,
        @ActiveLanguage Language language,
        @ActiveUser User user) {
    if (query != null) {
        return tagService.findTagsByQuery(user, query, limit, start, language, approved);
    } else {
        return tagService.findTags(user, limit, start, language);
    }
}

I'd also consider some edge cases for query, like the empty string or
a string with just whitespace for that matter.

Now for the unit tests, the naming could probably be improved, but I
also don't pay that much attention to it to be honest.

If the tagsList (or any other part like mocking methods etc.) is a
common thing in the tests consider moving it into the setUp method (or
equivalent) so it doesn't clutter up the test methods.

The assertSame is fine, you're basically just testing whether the
object is passed through directly, however the "not null" tests
afterwards are useless - tagsList shouldn't (can't) be null, so why
is it being verified here?

times(1) is default for Mockito, so leave it out.  Also the
verifyNoMoreInteractions is a bit discouraged in general since it
might make tests more brittle than they'd have to be, also since you're
not gaining much from it here I'd leave it out too.

IMO since this is at the outermost layer I'd rather have an integration
tests that actually checks the parameter parsing and validation too -
this particular test doesn't have that much value considering you're
just passing through values.


Find pairs in binary search tree in which sum of nodes keys is equal key There is a task:

  Given a binary search tree of \$n\$ nodes, find all the pair of nodes whose sum is equal to a given number \$k\$ in \$O(n)\$ time and constant space.

Please let me know if you find bugs on any data set.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    static class Node
    {
        Node(Node left, Node right, Node parent, int key)
        {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.key = key;
        }

        public Node left;
        public Node right;
        public Node parent;

        public int key;
    }

    public static void inOrder (Node node)
    {
        if(node.left != null) inOrder(node.left);
        System.out.println(node.key);
        if(node.right != null) inOrder(node.right);
    }

    public static Node successor (Node node)
    {
        Node successor = null;
        if(node.right != null)
        {
            node = node.right;
            while(node.left != null)
            {
                node = node.left;
            }
            successor = node;
        }
        else if(node.parent != null && node.parent.left == node) successor = node.parent;
        else if(node.parent != null && node.parent.right == node)
        {
            while(node.parent != null && node.parent.right == node)
            {
                node = node.parent;
            }
            successor = node.parent;
        }
        return successor;
    }

    public static Node predeccessor(Node node)
    {
        Node predecessor = null;
        if(node.left != null)
        {
            node = node.left;
            while(node.right != null)
            {
                node = node.right;
            }
            predecessor = node;
        }
        else if(node.parent != null && node.parent.right == node) predecessor = node.parent;
        else if(node.parent != null && node.parent.left == node)
        {
            while(node.parent != null && node.parent.left == node)
            {
                node = node.parent;
            }
            predecessor = node.parent;
        }

        return predecessor;
    }

    public static Node min (Node node)
    {
        while(node.left != null) node = node.left;
        return node;
    }

    public static Node max (Node node)
    {
        while(node.right != null) node = node.right;
        return node;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Node root = new Node(null, null, null, 5);//      5
        Node a = new Node(null, null, null, 2);   //     / \
        Node b = new Node(null, null, null, 1);   //    2   8
        Node c = new Node(null, null, null, 3);   //   /\    \
        Node d = new Node(null, null, null, 8);   //  1  3    9
        Node e = new Node(null, null, null, 9);   //

        root.left = a;
        root.right = d;
        a.parent = root;
        d.parent = root;

        a.left = b;
        a.right = c;
        b.parent = a;
        c.parent = a;

        d.right = e;
        e.parent = d;

        int sum = 10;

        //find pairs in Binary Search Tree in which sum of nodes keys is equal 10

        Node minnode = min(root);
        Node maxnode = max(root);
        while(minnode.key <= maxnode.key && minnode != maxnode)
        {
            if (minnode.key + maxnode.key == sum)
            {
                System.out.println("Pair found: " + minnode.key + " " + maxnode.key);
                minnode = successor(minnode);
                maxnode = predeccessor(maxnode);
            }
            else if(minnode.key + maxnode.key < sum)
            {
                minnode = successor(minnode);
            }
            else
            {
                maxnode = predeccessor(maxnode);
            }
        }
    }
}

I just have minor nitpicks.

1

You can simplify the methods for computing a successor/predecessor:

public static Node successor(Node node) {
    if (node.right != null) {
        return min(node.right);
    }

    while (node.parent != null && node.parent.right == node) {
        node = node.parent;
    }

    return node.parent;
}

Also, you compute the min(node.right) above in code; hence, you repeated yourself.

2

I would rip off the implementation of your sum pair algorithm out of main().

3

I would have a class, say, NodePair, which simply stores a pair of nodes.

4

The actual algorithm could just return the list of those NodePair objects.

5

Since you are printing the results, you could override toString() in NodePair and make it return a string in the format that meets your needs.

6

inOrder is not used. In case you don't need it either, consider removing it.

7

You import java.lang, yet you don't need to: it is imported by default. Also, you left hanging around two packages (java.util and java.io), remove them. Finally, I would encourage avoiding wildcard imports: import on individual basis, let people see what classes you use in your source.

Summa summarum

All in all, I had this in mind:

import java.util.ArrayList;
import java.util.List;

class Main {

    static class Node {

        Node(Node left, Node right, Node parent, int key) {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.key = key;
        }

        public Node left;
        public Node right;
        public Node parent;

        public int key;

        @Override
        public String toString() {
            return new StringBuilder("Node ").append(key).toString();
        }
    }

    public static Node successor(Node node) {
        if (node.right != null) {
            return min(node.right);
        }

        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }

        return node.parent;
    }

    public static Node predeccessor(Node node) {
        if (node.left != null) {
            return max(node.left);
        }

        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }

        return node.parent;
    }

    public static Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }

        return node;
    }

    public static Node max(Node node) {
        while (node.right != null) {
            node = node.right;
        }

        return node;
    }

    public static final class NodePair {
        public Node node1;
        public Node node2;

        public NodePair(Node node1, Node node2) {
            this.node1 = node1;
            this.node2 = node2;
        }

        @Override
        public String toString() {
            return new StringBuilder("[").append(node1)
                                         .append(", ")
                                         .append(node2)
                                         .append("]")
                                         .toString();
        }
    }

    public static List<NodePair> findPairsWithSum(Node root, int sum) {
        List<NodePair> nodePairList = new ArrayList<>();
        Node minnode = min(root);
        Node maxnode = max(root);

        while (minnode.key <= maxnode.key && minnode != maxnode) {
            if (minnode.key + maxnode.key == sum) {
                nodePairList.add(new NodePair(minnode, maxnode));
                minnode = successor(minnode);
                maxnode = predeccessor(maxnode);
            } else if (minnode.key + maxnode.key < sum) {
                minnode = successor(minnode);
            } else {
                maxnode = predeccessor(maxnode);
            }
        }

        return nodePairList;
    }

    public static void main(String[] args) throws java.lang.Exception {
        Node root = new Node(null, null, null, 5);//      5
        Node a = new Node(null, null, null, 2);   //     / \
        Node b = new Node(null, null, null, 1);   //    2   8
        Node c = new Node(null, null, null, 3);   //   /\    \
        Node d = new Node(null, null, null, 8);   //  1  3    9
        Node e = new Node(null, null, null, 9);   //

        root.left = a;
        root.right = d;
        a.parent = root;
        d.parent = root;

        a.left = b;
        a.right = c;
        b.parent = a;
        c.parent = a;

        d.right = e;
        e.parent = d;

        // Print all the node pairs summing to 10.
        for (NodePair pair : findPairsWithSum(root, 10)) {
            System.out.println(pair);
        }
    }
}

Hope that helps.

Edit

Actually, what comes to printing the node pairs, I realized that it makes sense to override Node.toString() as well. After that, building a string representation of a NodePair simplifies a bit. Please, for details refer to Node.toString and NodePair.toString.


Parse a tree & return the various paths Input:

{ 1: [2,3], 2:[4], 3: [5,6], 4:[6] }

Expected output:

[[1, 2, 4, 6], [1, 3, 5], [1, 3, 6]]

My Code:

def parse(node, tree):
    result = []
    if node not in tree:
        return [[node]]
    else:
        res = []
        for next_node in tree[node]:
            res.extend(parse(next_node, tree))
        for r in res:
           result.append([node]+r)
        return result

I'm looking for a less-complex solution.

You can get rid of the variables result and res and shorten the code by changing it into a generator. If you really need to get a list in the end, wrap the call with list(parse(root, tree)).

def parse(node, tree):
    if node not in tree:
        yield [node]
    else:
        for next_node in tree[node]:
            for r in parse(next_node, tree):
                yield [node] + r


Find string in sorted array with interspersed empty strings (from McDowell) Given a sorted array of strings which is interspersed with empty strings, find the location of a given string.
eg. "ball" in

{"at", "", "", "", "ball", "", "", "car",
            "", "", "dad", "",""}

would output 4

Any comments on the code below?

Also, correct me if I am wrong please:
- space complexity: in place
- time complexity: worst case O(n), average case O(log(n))

  public static int findString(String[] array, String target, int low, int high){
    if (high < low) return -1;

    int middle = (low+high)/2;

    if (array[middle].equals(target)) return middle;

    if (array[middle].equals("")){
      int left = middle;
      int right = middle;

      while (array[left].equals("") && left >= low) left--;
      while (array[right].equals("") && right <= high)  right++;

      if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);
      else if (array[right].compareTo(target) <= 0) return findString(array, target, right, high);
      else  return -1;
    }
    else{
      if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
      else if (array[middle].compareTo(target) <= 0) return findString(array, target, middle, high);
      else  return -1;
    }
  }

Bugs

To demonstrate some corner cases,
I will assume we have this convenient wrapper method (which I recommend to add anyway):

public static int findString(String[] array, String target) {
    return findString(array, target, 0, array.length - 1);
}

Given the input {"", "", "a"}, "0",
this code will result in ArrayIndexOutOfBoundsException:

  while (array[left].equals("") && left >= low) left--;

Because array[left] will be accessed after left becomes -1.
A quick remedy is to flip the operands of &&:

  while (left >= low && array[left].equals("")) left--;

But then, this line will fail too for the same reason:

  if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);

To prevent that, you would need to add the left >= low condition here too,
before accessing array[left]:

  if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);

Follow the same argument and fix for right too.

But actually this is still not enough.
In the above example input,
high will reach 0, low stays at 0,
and an infinite recursion occurs until a StackOverflowError.
so early in the function you need to add a condition on high == 0 too:

// ...

if (array[middle].equals(target)) return middle;
if (high == 0) return -1;

// ...

Unnecessary elements

This condition is unnecessary:

if (high < low) return -1;

The rest of the implementation automatically handles this case.

The last part of the function can be simplified:

else{
  if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
  else if (array[middle].compareTo(target) <= 0) return findString(array, target, middle, high);
  else  return -1;
}

This way is exactly the same, but simpler:

if (array[middle].compareTo(target) >= 0) return findString(array, target, low, middle);
return findString(array, target, middle, high);

Notice also that the >= 0 condition can be just > 0

Unit testing

To verify that your implementation works in the different cases,
especially the corner cases, it's good to have some unit tests, for example:

@Test
public void test_0x() {
    assertEquals(-1, findString(new String[]{"", "", "a"}, "0"));
}

@Test
public void test_0() {
    assertEquals(-1, findString(new String[]{"", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "a"));
}

@Test
public void test_z() {
    assertEquals(-1, findString(new String[]{"", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "z"));
}

@Test
public void test_a() {
    assertEquals(-1, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "a"));
}

@Test
public void test_ball() {
    assertEquals(4, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "ball"));
}

@Test
public void test_at() {
    assertEquals(0, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "at"));
}

@Test
public void test_car() {
    assertEquals(7, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "car"));
}

@Test
public void test_dad() {
    assertEquals(10, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "dad"));
}

@Test
public void test_core() {
    assertEquals(-1, findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "core"));
}

Coding style

It's recommended to use braces with even single-statement if, for and while statements too. So instead of:

if (array[middle].equals(target)) return middle;
if (high == 0) return -1;

This is better:

if (array[middle].equals(target)) {
    return middle;
}
if (high == 0) {
    return -1;
}

It's recommended to declare and initialize variables close to where they are actually used. So instead of:

int left = middle;
int right = middle;

while (left >= low && array[left].equals("")) left--;
while (right <= high && array[right].equals("")) right++;

if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);
else if (right <= high && array[right].compareTo(target) <= 0) return findString(array, target, right, high);
return -1;

This is better:

int left = middle;
while (left >= low && array[left].equals("")) left--;
if (left >= low && array[left].compareTo(target) >= 0) return findString(array, target, low, left);

int right = middle;
while (right <= high && array[right].equals("")) right++;
if (right <= high && array[right].compareTo(target) <= 0) return findString(array, target, right, high);
return -1;

And this is equivalent, but more efficient:

int left = middle;
while (left >= low && array[left].equals("")) left--;
if (left < low) return -1;
if (array[left].compareTo(target) >= 0) return findString(array, target, low, left);

int right = middle;
while (right <= high && array[right].equals("")) right++;
if (right > high) return -1;
if (array[right].compareTo(target) <= 0) return findString(array, target, right, high);

Instead of .equals(""), it's better to use .isEmpty().


Implementing F1 score I am trying to implement the F1 score shown here in Python.

The inputs for my function are a list of predictions and a list of actual correct values.  I thought that the most efficient way of calculating the number of true positive, false negatives and false positives would be to convert the two lists into two sets then use set intersection and differences to find the quantities of interest.  Here is my code

def F1_score(tags,predicted):

    tags=set(tags)
    predicted=set(predicted)

    tp=len(tags.intersection(predicted))
    fp=len(predicted.difference(tags))
    fn=len(tags.difference(predicted))

    if tp>0:
        precision=float(tp)/(tp+fp)
        recall=float(tp)/(tp+fn)

        return 2*((precision*recall)/(precision+recall))
    else:
        return 0

To compute the length of a set difference, you only need to subtract the length of the intersection from the length of the set.
You could make use of the intersection when computing the differences. Subtracting the intersection gives the same result but processes fewer elements.

tags = set(tags)
predicted = set(predicted)

tp = len(tags & predicted)
fp = len(predicted) - tp
fn = len(tags) - tp

Note that I added spaces around operators to improve readability. I also used the & operator instead of the intersection method as a matter of preference.


Filter by date method This method allows me to filter by date a data structure list of hash that contains articles. I would like to have your opinion on the code:

=method article_by_date

    $articles->articles_by_date( month => 12 );

Return a list of articles filter by date specified:

    input: month (Int) : optional, month to match
           year (Int) : optional, year to match
    output: Hashref: Details of article

=cut

sub articles_by_date {
    state $check = compile(
        $invocant,
        slurpy Dict[
            month => Optional[Int],
            year  => Optional[Int],
        ]
    );
    my ($self, $arg) = $check->(@_);
    my $month = $arg->{month};
    my $year  = $arg->{year};

    if ( ! defined($year) ) {
        my $dt = DateTime->now;
        $year  = $dt->year;
    }

    my $date  = defined($month)
        ? qr/^\d\d\/$month\/$year\s\d\d:\d\d:\d\d$/
        : qr/^\d\d\/\d\d\/$year\s\d\d:\d\d:\d\d$/;

    my @articles;
    foreach my $article ( @{$self->_get_or_create_cache('articles')} ) {
        $article->{date} =~ $date
            and push(@articles, $article);
    }

    return \@articles;
}

Most of this depends on what exactly do you want to achieve. For example, @articles will be a list of references to the same articles that are also referenced in $self->_get_or_create_cache('articles'). Depending on what you want, you might want to clone these values, instead of just pushing them to @articles.

The other thing is a regex for dates. Are you certain that your dates will be, for example, 23/08/2013, and not 23/8/2013? If not, this might be better:

my $date  = defined($month)
    ? qr/^\d{1,2}\/$month\/$year\s\d{1,2}:\d{1,2}:\d{1,2}$/
    : qr/^\d{1,2}\/\d{1,2}\/$year\s\d{1,2}:\d{1,2}:\d{1,2}$/;

The same goes for the times, of course.

Depending on how clean your input is, you might want to replace $month and $year with \Q$month\E and \Q$year\E to avoid matching special characters in those variables (i.e., that . is matched as a dot and not as any character).

If it may be possible for the input to have extra spaces, you might want to add \s* after ^ and before $, while also replacing \s behind $year with \s+.

Day of month can be more precisely matched as (0?[1-9]|[1-2]\d|3[01]) (similar for months, hours, minutes, and seconds), but this makes regexes quite comples, so see if you need this.


Word VBA function to find a specified heading & return its text as a string In this post, I asked for an overall review of a script to auto-generate table captions, because it was running relatively slowly. I've used Debug.Print to isolate the problem, and this function takes the longest (at 16 seconds).

The purpose of the function is to find the heading of a specified style that the selected text falls under. It loops back through each paragraph to see if it's the right style. When it finds it, it returns the paragraph text as a string (which the larger script uses to generate the table caption).

Any suggestions for improvement are welcome, but I'd specifically like performance improvement suggestions, as well as feedback on how long a function like this should take (i.e., is it slow or am I just impatient?)

Public Function FindHeading(strHeadLevel As String) As String
'Gets the heading level as an input and finds the closest heading of that level before the selection.

    Dim rngSelection As Range
    'the initial selection

    Dim rngPrev As Range
    'The current paragraph to be evaluated.

    Set rngSelection = Selection.Range
    Set rngPrev = rngSelection.Previous(wdParagraph, 1)

    'MsgBox (rngPrev.Text)

    Do While rngPrev.Style <> strHeadLevel

        If ActiveDocument.Range(0, rngPrev.Paragraphs(1).Range.End).Paragraphs.Count > 1 Then
            Set rngPrev = rngPrev.Previous(wdParagraph, 1)
            'MsgBox ("rngPrev Style =  " & rngPrev.Style & vbCr & "Text = " & rngPrev.Text)
        Else
            'MsgBox ("Heading not found")
            Exit Do
        End If

    Loop

    If rngPrev.Style = strHeadLevel Then
        FindHeading = rngPrev.Paragraphs(1).Range.Text
    Else
        FindHeading = "No heading found"
    End If

End Function

No need for a loop at all; just use Word's built-in ability to find text based on its style and other formatting.

Like so:

Public Function FindHeading(strHeadLevel As String) As String
    Dim rng As Range

    'set a range to the selection first so we can avoid
    '  the selection jumping around as we do our find
    Set rng = Selection.Range

    With rng.Find
        'set up our find criteria
        .ClearAllFuzzyOptions
        .ClearHitHighlight
        .ClearFormatting
        .Text = ""
        'search from current location back to start of document
        .Forward = False
        'and stop when we hit the start
        .Wrap = wdFindStop
        'here's the important part
        .Format = True
        .Style = strHeadLevel

        'now do our find
        If .Execute Then
            '.Parent contains the found range
            Set rng = .Parent
            'strip off trailing paragraph mark
            rng.MoveEnd unit:=wdCharacter, Count:=-1
            'grab the text of the found range
            FindHeading = rng.Text
        Else
            'we ain't got nothing
            FindHeading = "No heading found"
        End If
    End With
End Function


Efficient binary patcher I am currently working on a little binary patcher. My current code works fine but I do want my code to be optimized (fast) and as clean as possible. Could you all please help me review this?

IDE: Delphi 7 and XE7

const
  OriginalByte: array [0 .. 55] of Byte = ($64, $69, $6E, $67, $20, $6D, $65,
    $20, $68, $69, $73, $00, $00, $00, $00, $27, $00, $00, $28, $00, $00, $00,
    $21, $00, $00, $00, $63, $6F, $6D, $70, $75, $74, $65, $72, $2E, $00, $00,
    $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $27, $00, $00, $28,
    $00, $00, $00, $00);

  BytetoWrite: array [0 .. 55] of Byte = ($63, $68, $6F, $67, $20, $6D, $65,
    $20, $68, $69, $73, $00, $00, $00, $00, $27, $00, $00, $28, $00, $00, $00,
    $21, $00, $00, $00, $63, $6F, $6D, $70, $75, $74, $65, $72, $2E, $00, $00,
    $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $27, $00, $00, $28,
    $00, $00, $00, $06);

function CompareByteArrays(FirstArray, SecondArray: array of Byte): Boolean;

var
  Counter: Integer;
begin

  Result := True;
  if Length(FirstArray) <> Length(SecondArray) then
  begin
    Result := False;
    Exit;
  end;

  for Counter := Low(FirstArray) to High(FirstArray) do

  begin
    if (FirstArray[Counter]) <> (SecondArray[Counter]) then
    begin
      Result := False;
      Exit;
    end

  end;

end;

procedure DoMyPatch();
var

  i: Integer;
  FileName: string;
  input: TFileStream;

  FileByteArray, ExtractedByteArray: array of Byte;

begin
  FileName := 'Cute1.res';

  try
    input := TFileStream.Create(FileName, fmOpenReadWrite);
  except
    on E: Exception do
    begin
      ShowMessage(E.Message);
      Exit;
    end
  end;

  input.Position := 0;
  SetLength(FileByteArray, input.size);
  input.Read(FileByteArray[0], Length(FileByteArray));
  for i := Low(FileByteArray) to High(FileByteArray) do
  begin

    ExtractedByteArray := Copy(FileByteArray, i, Length(OriginalByte));

    if CompareByteArrays(ExtractedByteArray, OriginalByte) = True then
    begin
      // Begin Patch
      input.Free;
      try
        Win32Check(CopyFile(PChar(FileName), PChar(ChangeFileExt(FileName,
          '.BAK')), False));
      except
        on E: Exception do
        begin
          ShowMessage(E.Message);
          Exit;
        end
      end;

      try
        input := TFileStream.Create(FileName, fmOpenReadWrite);
      except
        on E: Exception do
        begin
          ShowMessage(E.Message);
          Exit;
        end
      end;

      input.Seek(i, SoFromBeginning);

      input.Write(BytetoWrite[0], Length(BytetoWrite));

      ShowMessage('Patch Success');
      input.Free;
      Exit;
    end;
  end;
  ShowMessage('Patch Fail');

  input.Free;

end;

Some notes:

add definition of the undeclared variables BytetoWrite, OriginalByte and how they are used/initialized
format your code for better readability. Left indentation is not aligned. Too many void blank lines
using

resource := CreateResource;
try
    // do something
finally
    FreeAndNil(resource);
end

pattern is easy to follow and it prevents unintended memory leaks nicely
for byte-to-byte memory compare in CompareByteArrays better use built-in CompareMem function instead of custom array traversal. In an old language runtime source codes this function was implemented in optimized assembly language
using Integer for file-offset is not very future-friendly idea considering that it is normal (for average end-user) today to work with video files in 4K resolution where single file size can be >4GB
using Memory Mapped Files for read-only file access will give you simpler code (whole file is an in-memory array) and faster I/O operations (on-demand reading managed by OS kernel code). This method can give you significant boost if the original file is big and the searched-pattern is located near the beginning of the file
the loop should end at High(FileByteArray) - Length(OriginalByte) (+/-1) as beyond this boundary the pattern can not be found anyway
you can get some speed by comparing against the original byte array just offset by the i index. Creation of the intermediate ExtractedByteArray would not be necessary (throw away, safe some memory allocation and memory copy CPU-clocks). Like this:

if CompareByteArrays(ExtractedByteArray, OriginalByte) = True then

if CompareMem(@FileByteArray[i], @OriginalByte[0], Length(OriginalByte)) = True then

assuming the i...i + Length(OriginalByte) - 1 boundaries are withing the range Low(FileByteArray)...High(FileByteArray) as mentioned in (7)


C++ simple password-protected console app I have been reading about passwords and hashing algorithms and what not and decided to write a program.

Overview: The user should be prompted to create a password the first time the program is executed. They should enter a key and confirm it. If they have executed the program previously, then they should just enter the password to gain access.

I determine if the user has run the program by checking if key.txt exists. Is there a more preferred method?

I tried to streamline some code with the two bool functions. Any other suggestions for cleaner or more concise code?

#include <iostream>
#include <fstream>
#include <string>
#include "sha256.h"
using namespace std;

bool keyExists() {
    bool keyExists = false;
    ifstream inFile("key.txt");

    if (inFile) {
        keyExists = true;
    }

    return keyExists;
}

bool isMatch(string key, string confirmKey) {

    bool match = false;
    if (key == confirmKey) {
        match = true;
    }

    return match;
}

int main() {

    if (keyExists()) {
        string key;
        string storedKey;
        cout << "Please enter key: ";
        getline(cin, key);

        SHA256 sha256;
        ifstream inFile("key.txt");
        getline(inFile, storedKey);

        if (isMatch(sha256(key), storedKey)) {
            cout << "Acces Granted!\n";
        }
        else {
            cout << "Access Denied!\n";
        }
    }

    else {
        string key;
        string confirmKey;

        cout << "Please create a key: ";
        getline(cin, key);
        cout << "Confirm key: ";
        getline(cin, confirmKey);

        if (isMatch(key, confirmKey)) {

            SHA256 sha256;
            ofstream outFile("key.txt");
            outFile << sha256(key);
        }

        else {
            cout << "Keys do not match!\n";
        }
    }

    return 0;
}

Many thanks to Stephan Brumme for the awesome hashing algorithm code! This was very easy to implement.

Using namespace std isn't a good practice in header files, where your program should at least partially reside, because you introduce potential name conflicts. So don't do that, and prefix the names you're importing with std::, you'll get used to it in no time.
Your function keyExists can be improved upon. First, its name is not the best you could have found, because it suggests you're looking for the existence of a particular key, whereas what you really want to know if the program has been launched before. So is_first_use, or is_first_visit as an analogy to a website, would tell more. Besides, it doesn't have to be that verbose:

Original version

bool keyExists() {
    bool keyExists = false; // the homonymy is a bad idea
    ifstream inFile("key.txt");

    if (inFile) {
        keyExists = true; //
    }

    return keyExists;
}

first trimming

bool keyExists() {
    bool keyExists = false;
    ifstream inFile("key.txt");

    keyExists = inFile; // because streams can be converted to bool as you know

    return keyExists;
}

second trimming

bool keyExists() {
    ifstream inFile("key.txt");
    return inFile; // you specified the return type, so the conversion will occur
}

third trimming

bool keyExists() {
    return ifstream("key.txt"); // no need for a named object
}

So do you really need a function? It depends. If you want to let your program evolve from here, it's a good idea to keep the function, and implement a more viable test at a later point without disturbing the rest of your code. Otherwise it isn't worth the burden of finding a name for it.

Your function isMatch suffers from the same issue.

original version

bool isMatch(string key, string confirmKey) {

    bool match = false;
    if (key == confirmKey) {
        match = true;
    }

    return match;
}

suggested implementation

bool isMatch(const string& key, const string& confirmKey) { // pass it by reference to avoid a potentially costly copy
    return key == confirmKey; // no need to store that in a `bool` before returning it
}

Then again I'm not sure it needs a function of its own...

What's a valid key?

It might be a design choice, but it's very rare to allow for tabs, spaces and such inside a password. Is this really what you want? Is it compatible with every way to store passwords that you can think of? How would you constrain the choice of a password?


Hex to integer converter I've just coded a hex to integer converter in C and want my code criticized. I did not cover switch statements so I know that can be improved.  I am also planning to truncate "0x" in the beginning of the input if the user enters that.

#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define MAXCHAR 100

int htoi(char hexArray[], int srraySize);

int main(void){
    int userInput;
    int i = 0;
    char hexArray[MAXCHAR];

    while((userInput = getchar()) != EOF){
        if(userInput >= '0' && userInput <= '9'){
            hexArray[i] = userInput;
            ++i;
        }

        if((userInput >= 'a' && userInput <= 'f') || (userInput >= 'A' && userInput <= 'F')){
            hexArray[i] = userInput;
            ++i;
        }
    }

    hexArray[++i] = '\0';

    int ans = htoi(hexArray, i);

    printf("%d\n", ans);

    return 0;
}

int htoi(char hexArray[], int arraySize)
    typedef enum{ a = 10,
        b,
        c,
        d,
        e,
        f
        } hexValues;

    int intArray[MAXCHAR] = { 0 };
    int i, j;
    int finalAns = 0;

    for(i = 0; i < arraySize; ++i){
        if(hexArray[i] >= 'A' && hexArray[i] <= 'F'){
            hexArray[i] = (char)tolower((int)hexArray[i]);
        }
    }

    for(i = 0; i < arraySize; ++i){
        if(hexArray[i] >= '0' && hexArray[i] <= '9'){
            intArray[i] = hexArray[i];

        } else if(hexArray[i] >= 'a' && hexArray[i] <= 'f'){
            if(hexArray[i] == 'a'){
                intArray[i] = a;
            } else if(hexArray[i] == 'b'){
                intArray[i] = b;
            } else if(hexArray[i] == 'c'){
                intArray[i] = c;
            } else if(hexArray[i] == 'd'){
                intArray[i] = d;
            } else if(hexArray[i] == 'e'){
                intArray[i] = e;
            } else if(hexArray[i] == 'f'){
                intArray[i] = f;
            }
        }
    }

    j = arraySize-2;

    for(i = 0; i < arraySize-1; ++i){
        printf("J = %d\n", j);
        printf("Initial Value: %d\n", intArray[i]);
        intArray[i] = (intArray[i] * (pow(16, j)));
        printf("Processed Value: %d\n", intArray[i]);
        finalAns = finalAns + intArray[i];
        --j;
    }

    return finalAns;
}

Your hexArray has a static size of MAXCHAR but you never check if you didn't exceed this size when reading input. Consider what would happen if someone enters MAXCHAR+1 characters at input.
When you set last character in your hexArray to '\0', you do it on wrong position. In your while loop, you increment i after each write to hexArray so at the end i is an index of next free element. And you should write '\0' here. But you use pre-increment (++i) so you write this '\0' on next place.
This '\0' is not really needed at all since you pass array size as an argument to htoi anyway. But you pass wrong size as I already mentioned.
You are using tolower function in your htoi function but you could do this already when getting input. This saves you one loop over all values. It means that htoi will be less general since it will only work with low capital letters, though.
You could also use tolower function on all the input characters since if tolower gets argument that is not uppercase letter, it will return unchanged value. This would save you some ifs in your code for the price of overhead of running a function (and doing ifs in it since it has to do this).
if(hexArray[i] >= '0' && hexArray[i] <= '9') intArray[i] = hexArray[i]; is wrong. You set intArray[i] value to '0' (which is numerical value 48) instead of 0. So you should use intArray[i]=hexArray[i]-'0'; instead.
Your big if-elseif block for a-f characters can be much simpler. All ASCII letters have consecutive numbers so to convert 'a' to 10, 'b' to 11 etc you can use:

  else if(hexArray[i] >= 'a' && hexArray[i] <= 'f') {
      intArray[i] = hexArray[i] - 'a' + 10;
  }

This saves you a lot of ifs and you can even remove your enum.
The whole intArray array is not really needed at all since you could do your computations inside of the loop in which you create it. This way you can have only one loop inside of your htoi.
Yyou are using int type to hold computed integer. So you can really only convert sizeof(int)*2 characters long hex value inside, and your MAXCHAR=100.
You can eliminate the need of pow function if you will start your calculations from the end of intArray array. You can store powers of 16 in some variable and just multiply it by 16 (or shift left 4 bits) in each iteration.


Stack Implementation in Scala I would like to get feedback on my code for Stack implementation written in scala. What can be improved to make it more like scala code. What important helper functions am i missing?
class StackDS[A] {
  private var list: List[A] = List[A]()

  def push(ele: A) =
    list = ele :: list

  def pop = {
    val pop = list.head
    list = list.tail
    pop
  }

  def size: Int = {
    list.size
  }

}

layout - The code is clear and easy to read but I find your use of blank lines a bit excessive.
braces - Both the push() and size methods consists of a single line of code so surrounding braces, {..}, are optional. You drop them in one and keep them in the other. Inconsistent.
types - The size method declares its return type but push() and pop don't. It's usually a good idea to include them in all but the smallest, simplest method definitions.
mutation - The mutating collection, list, is kept local and private, which is good. I might argue that it's better to keep a mutable collection, such as Buffer for example, in a val variable instead of keeping an immutable collection, List, in a var variable.
mutating methods - For methods with no arguments that mutate an internal state, such as pop does, the Scala Style Guide recommends declaring the method with empty parentheses, def pop() ..., as an indicator to the end user.
safety - The code will throw an exception if you try to pop an empty stack. That may be as you want it. I prefer methods that return Option[A] instead of throwing.
convenience - If I was trying to use StackDS in my code, I'd want to know why stacks have to be created empty. Why can't I create a populated stack? e.g. new StackDS(8,4,11) It would require a small modification to the existing code.
What I think your code clearly demonstrates is that a simple List does most of what we need from a Stack. So even though the Standard Library includes a full featured Stack implementation, it's not often used.


Adding dynamic column names to a table I'm using Microsoft SQL Server 2014 Express.

I found myself wanting to add the Columns CompanyNameChangeDate (1 through 10) and CompanyNameChangePreviousName (1 through 10) to a table in my database.

I wrote the following query to do it:

declare @i int
set @i = 0

Declare @nameChangeDatePrefix as varchar(255) = 'CompanyNameChangeDate'

Declare @nameChangePreviousNamePrefix as varchar(255) = 'CompanyNameChangePreviousName'

declare @sql as varchar(255)

while (@i < 10)
begin
    set @i = @i + 1

    set @sql = 'ALTER TABLE company_registry_data ADD ' + @nameChangeDatePrefix + Cast(@i as varchar(255)) + ' DATE'
    execute(@sql)

    set @sql = 'ALTER TABLE company_registry_data ADD ' + @nameChangePreviousNamePrefix + Cast(@i as varchar(255)) + ' VARCHAR(255)'
    execute(@sql)
end

How could I make it better?
What naming conventions have I contravened?
What habits should I start building right now?
What are the code smells?

I would consider your whole proposal for this schema to be a code smell. In SQL, if there are many data to be treated alike, they should be stored in one column, rather than in multiple columns.  If you store your data using this proposed schema, any code that tries to use the schema is likely to be nasty too. (What's the average time interval between name changes? Good luck writing that query!) You would also have an arbitrary limit of 10 name changes per company, and accommodating more names would necessitate another schema change!

Therefore, it would make more sense to have a CompanyNameChange table, with (companyId, changeDate) as the primary key, and additional attributes previousName as an additional attribute.  If, for some reason, you do need the data to be presented in that proposed tabular format, you could always perform some joins.


Allowing "plugin" programmers to subscribe to messages I am having difficulty deciding how to implement an exception handling strategy.

I am using an observer pattern to allow "plugin" programmers to subscribe to Messages. These subscribers generally log a unique error (and do some other stuff) under an exceptional circumstance during handling the message. The code snippet below is an example of what a common implementation (and its interface) looks like:

// API interface
interface IMessageListener {
   void onMessage(Message m);
}

class StuffMessageListener implements IMessageListener {
    ...

    @Override void onMessage(Message m) {

        try {
            Stuff s = stuffDAO.getStuff(..); // throws SQLException

            ...

            m.reply(true);
        } catch (SQLException e) {
            // if an exception happens, log it, and reply to the message
            log.error(A_UNIQUE_ERROR_CODE, e);
            m.reply(false);
        }
    }
}

What irks me is that the catch block has become very redundant code, copied throughout 95% of the ~50 existing listeners. Can we come up with something better?

A good solution should:

be easy to use/understand for an amateur programmer
keep the programmer aware of the existence/potential of exceptions
minimize the chance of a programmer accidentally "swallowing" an exception
reduce the amount of "boilerplate" code

There is a subtle requirement needed for the solution. The UNIQUE_ERROR_CODE should be unique across all declarations of the listeners. That way, I could gain statistics based upon where the error was caught across all listeners.

If the UNIQUE_ERROR_CODE is buried underneath an abstract class, or is used outside onMessage(..), I will lose the needed "uniqueness."

Allow throwing exceptions

Do you really think your user is capable of handling all the exceptions?

interface IMessageListener {
   void onMessage(Message m) throws Exception;
}

Of course if some plugin wants to handle the exception, nothing prevents he/she of using try/catch. But no one is forced to do so and if, according to your knowledge, the catch block is almost always the same, put it outside in the code calling onMessage().

Give your user a simplified adapter

abstract class ThrowingMessageListenerAdapter implements IMessageListener {

    @Override
    public void onMessage(Message m) {
        try {
            doOnMessage(m);
        } catch (SQLException e) {
            // if an exception happens, log it, and reply to the message
            log.error(A_UNIQUE_ERROR_CODE, e);
            m.reply(false);
        }
    }

    protected abstract void doOnMessage(Message m) throws Exception;

}


Review my jQuery plugin structure I'm trying to learn learning javascript and jQuery plugin standards, and after some googling and testing I've come up with this pattern:

;(function(window, document, $, undefined){
  var plugin = function(element){
    var instance = this,
        somePrivateFunc = function(){
          console.log(instance.options);
        };

    this.options = $(element).data();
    this.publicFunc = function(){
     somePrivateFunc();
    };
  }

  $.fn.myplugin = function(){
    return this.each(function(){
      if(!$(this).data('_myplugin')){
        var myplugin = new plugin(this);
        myplugin.publicFunc();
        $(this).data('_myplugin', myplugin);
      }
    });
  }

}(window, document, jQuery));

Example

http://jsfiddle.net/4NAXb/

Is this OK? Do you have any suggestions on improving it? Thanks!

Here are some suggestions:

Use $.data(this, '_myplugin') & $.data(this, '_myplugin', myplugin). They're SO MUCH faster.
Since you call .publicFunc every time you instantiate your plugin, you should probably move the call into your constructor instead.
Public functions should be assigned to the prototype, so that we don't create a new function every time we create a new instance.
Likewise, define a private function outside of the constructor, in the parent closure. Again, we don't want to have to re-create the same function over and over again.

;(function ( window, document, $ ) {

  function somePrivateFunc ( instance ) {
    console.log( instance.options );
  }

  var Plugin = function( element ) {
    // What is this?
    this.options = $(element).data();
    this.publicFunc();
  }

  Plugin.prototype.publicFunc = function () {
   somePrivateFunc( this );
  };

  $.fn.myplugin = function () {
    return this.each(function () {
      if ( ! $.data(this, '_myplugin') ) {
        $.data( this, '_myplugin', new Plugin(this) );
      }
    });
  };

}(window, document, jQuery));

P.S. You haven't described how you're exposing the plugin's additional methods. For that you should read the jQuery plugin creation tutorial.

Find the section titled Provide Public Access to Secondary Functions as Applicable.


64-bit Mersenne Twister random-number generator; follow-up #1 This question is a direct follow-up of:

Have a look at this Mersenne Twister random-number generator function

Thanks to Code Review and Stack Overflow, I now realize, that:

unsigned long long int is not guaranteed to be 64-bit
I don't want to re-initialize the random_device on every function call

and a few other things.

So, based on current information, I've re-written it as follows:

#include <iostream>     // std::cout
#include <cstdint>      // std::uint64_t
#include <random>       // std::random_device, etc.

std::uint64_t random_integer(std::uint64_t rand_min, std::uint64_t rand_max)
{
    // use Mersenne Twister as random-number generator engine
    // initialize = seed the random device; static thread_local = only once
    // avoid "most vexing parse" by using "uniform initialization syntax" = { something{}() }
    static thread_local std::mt19937_64 random_number_generator{std::random_device{}()};

    // uniform number distribution, guaranteed unbiased
    std::uniform_int_distribution<std::uint64_t> number_distribution(rand_min, rand_max);

    // return one random number
    return number_distribution(random_number_generator);
}

// this is just to test the output
int main()
{
    for (int i = 1; i <= 10; i++)
    {
        std::cout << random_integer(10000000, 100000000) << std::endl;
    }
    return 0;
}

If you could guide me further on improving it, I would be grateful.

Don't pay for what you don't use

I can imagine many situations where using the generator from one and only one thread would be quite reasonable. In that case, users would pay on each call to the function. It is one of the reasons why I prefer objects in these cases: it gives gun to hands of the users. Whether they shoot their foot or what they want to shoot is not my business any more. Though it is not excuse to make "easy to use incorrectly" interfaces.

C with classes interface

I'm not really sure why, but the exact kind of interfaces are prevalent. May be it is because I learnt modern C++ before learning anything else. Modern ways of doing things should come to mind first, and if they are not good fit, start searching for something else.

Modern (almost?) interface

Lets reconsider the interface (given you figured out how to share state, which leads to object):

template <typename ForwardIterator>
void generate_range(ForwardIterator first, ForwardIterator last)
{
    //state sharing mechanism

    while (first != last)
    {
        *first++ = number_distribution(random_number_generator);
    }
}

This enables following syntax:

std::vector<int> v(20);
generate_range(v.begin(), v.end());

But this requires resizing. Some people even might want to print 10 integers into something, like in your example. Lets handle that too:

template <typename OutputIterator>
void generate_some(OutputIterator d_first, std::size_t n)
{
    for (std::size_t i = 0; i < n; ++i)
    {
        *d_first++ = number_distribution(random_number_generator);
    }
}

This enable following:

generate_some(std::ostream_iterator<int>{std::cout}, 10);

Or, if you want to append into vector:

std::vector<int> v;
generate_some(std::back_inserter(v), 10);

And, just for symmetrical and intuitive interface:

generate_one()
{
    return number_distribution(random_number_generator);
}

Of course in all of the examples you'll get narrowing conversion warning, I was just too lazy to type out std::uint64_t (I don't have IDE autocomplete here). Also, maybe putting static_assert to check iterator types will output much better compilation error message.

User experience

Yes, yes, user experience. It is not only about graphical interfaces. What experience do you want your users to have? What use cases do they have? Usually you have a problem, then solve it. Creating an interface without use cases in mind is like solving non-existent problem.

I would design an interface using this algorithm:

Write usages out in declarative form
Write out some candidates
If list is empty, make usages more concrete, go back to 1
Narrow/order list based on "easy to use correctly, hard to use incorrectly"
Order the list based on implementation complexity
Start implementing from first to last, until the first working version
Think if they'll ever need more control, stop if not.
Port/factor out core functionality which has greatest amount of control, and base the interface on top of it. Usually template parameters with default arguments, function with default arguments, using declarations help. I've yet to see the cases where it would be impossible.


How can I refactor to avoid repetition finding the index of strings in a list? I have a list of strings where I want to find the index of a first- and second-choice video compressor.

Logic: If the first choice is available, return its index. If not, and the second choice is available, return its index. If not, return zero.

Here is what I have now:

List<string> availableVideoCompressors = GetAvailableVideoCompressors();
int compressorIndexToUse = 0;
if (availableVideoCompressors.Any(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase)))
    compressorIndexToUse = availableVideoCompressors.Select((c, i) => new { c, i }).First(c => c.c.Equals("ffdshow", StringComparison.OrdinalIgnoreCase)).i;
else if (availableVideoCompressors.Any(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)))
    compressorIndexToUse = availableVideoCompressors.Select((c, i) => new {c, i}).First(c => c.c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)).i;
return compressorIndexToUse;

The problem is that I am iterating the list several times. Once to determine if the desired compressor is available, then again to obtain its index, for each candidate compressor.

I am not sure how to refactor to avoid this repetition. What can I do instead?

Let's start with a simpler problem where there's just one choice:

for (var i = 0; i < compressors.Count; i++)
{
    if (compressors[i].StartsWith(firstChoice, StringComparison.OrdinalIgnoreCase))
    {
        return i;
    }
}

return 0;

(I would much prefer returning -1 if no match is found, but requirements are requirements.)

Now we can build on top of this to deal with the second preference:

var secondChoiceIndex = -1;
for (var i = 0; i < compressors.Count; i++)
{
    if (compressors[i].StartsWith(firstChoice, StringComparison.OrdinalIgnoreCase))
    {
        return i;
    }

    if (secondChoiceIndex == -1 && compressors[i].StartsWith(secondChoice, StringComparison.OrdinalIgnoreCase))
    {
        secondChoiceIndex = i;
    }
}

return secondChoiceIndex == -1 ? 0 : secondChoiceIndex;


Delete matching ID and insert new data Delete all matching ID
Insert new data

function add_date($id,$date) {

mysql_query("DELETE FROM wp_opening_date WHERE Id='$id'");
$dates = explode(",",$date);
foreach ($dates as $date) {
    $date = explode("/",$date);
    $d    = $date[0];
    $m    = $date[1];
    $y    = $date[2];
    mysql_query("INSERT INTO wp_opening_date (Id, D, M, Y) VALUES ('$id','$d', '$m', '$y')");
}
mysql_close();

}

And i using function like this

$id = '277';
$dates = '01/10/2012,28/11/2012,27/11/2012,29/11/2012';
add_date($id,$dates);

Review my code + idea pls

The idea i will searching Ids by month or year or date

Well, there's nothing wrong as far as I can see here. The only thing I would check is that there is a suitable index on the Id field in database, so the delete query can be performed relatively quick.

Another thing to consider is the size of your table. If you have lots of records in there, it can take considerable time to remove and re-add records again (due to indexing and re-indexing upon each delete/insert). In such case, I would simply add a flag to the database, marking those old dates as deleted and simply add new ones at the end of the table.

Yet another thing that comes to my mind now is that you can gain even more performance-wise if you grouped those single inserts like so:

$vals = array();
foreach ($dates as $date) {
    $date = explode("/",$date);
    $d    = $date[0];
    $m    = $date[1];
    $y    = $date[2];
    $vals[] = "('$id', '$d', '$m', '$y')";
}
mysql_query("INSERT INTO wp_opening_date (Id, D, M, Y) VALUES ".implode(',', $vals));

At last, please do not use mysql_* functions, they are now deprecated. See the PHP manual for mysql_query for more info.


Ruby solution to Project Euler Problem #4: Largest palindrome product I've solved the Project Euler Problem #4, but I'd like some tips as to how to make this more efficient. I am a beginner to Ruby, so please be nice about the stupid stuffs (but still tell me about it).
Project Euler 4: Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
1

class Euler4
  def isPalindrome(n)
    n == n.to_s.reverse.to_i
  end
end

  puts "Setting Variables"
  x = 999
  y = 999

  highest = 1

  found = false

  while (x > 100 && !found)
    y = 999
    while (y > 100 && !found)
      puts "Working with"
      puts x
      puts " and "
      puts y

      if Euler4.new.isPalindrome(x*y)
        puts "Found Palindrome"
        puts x
        puts y
        puts x*y
        if highest < (x*y)
          highest = x * y
        end
      end
      y = y - 1
    end

    x = x - 1

  end

puts "Highest Found"
puts highest

Let's start with something small:

def isPalindrome(n)
  n == n.to_s.reverse.to_i
end

How do I know if a number is a palindrome?

Convert it to a string.
Produce the reverse of that string.
Convert the reversed string to a number.
Compare the numbers for equality.

As yourself: why did we need to do the last two steps?  We could have said:

Convert it to a string.
Produce the reverse of that string.
Compare the strings for equality.

and skipped the "convert to integer" step entirely.

Next small thing. I've removed every line of your program that does not use variable found:

found = false
while (x > 100 && !found)
  while (y > 100 && !found)

See any problems with that code? Because I don't see anywhere that it is set to true and therefore it will always be false. I'm not sure why a variable that is always false is of use to you.

Next thing: You check all pairs: (999, 999), (999, 998), ... (999, 101) and then start over again with (998, 999).  But you already checked (998, 999) when you checked (999, 998)! You don't need to start y at 999.  It suffices to start y at x.  Then you only check each pair once instead of checking the vast majority of them twice.

Next thing: If you find an (x, y) pair that is a palindrome, you don't need to check (x, y - 1); even if it is a palindrome, it will be smaller. Probably this is what you were trying to do with your "found" variable, but you never wrote the logic correctly.

Next thing: Remove all that print-debugging trace. If you need to debug your program, use a debugger.


ToString() and AddString() method without using .Net Collections I was asked to answer the following question before setting up a phone interview, but they said my code wasn't detailed enough.

Question:

  Without using any of the .NET Collection or Linq libraries (i.e.
  without using List), implement a ListOfStrings object that
  contains a set of strings. This object has the following methods:
  Add(string) - inserts a string to the end of the list ToString() -
  Returns the list as a comma separated string.

  Example Usage:

ListOfStrings list = new ListOfStrings(); // set is empty
list.Add("abc"); // set is "abc"
list.Add("xyz"); // set is now "abc", "xyz"
list.Add("123"); // set is now abc", "xyz", "123"
list.ToString(); // Should return "abc,xyz,123"

  Ideally, this code should be able to handle large numbers of items.

Answer:

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                ListOfStrings ls = new ListOfStrings();
                ls.Add("test1");
                ls.Add("test2");
                ls.Add("122");
                ls.Add("");
                ls.ToString();
                Console.WriteLine(ls.ToString());
            }
        }
    }

    public class ListOfStrings
    {
        private string ListOfString;

        public ListOfStrings()
        {
            ListOfString = null;
        }
        public string Add(string input)
        {
            if (input != string.Empty)
            {
                ListOfString = ListOfString == null ? input : ListOfString + "," + input;
            }
            return ListOfString;
        }

        public string ToString()
        {
            return ListOfString;
        }
    }
}

Please let me know feedback on the code.

ListOfString = null; is useless, fields get initialized to default(T) which is null for reference types. So you can drop the constructor.

For simple initializations you can use inline initializers. e.g.

private string ListOfString = "";

You're hiding ToString() instead of overriding it.
You're ignoring empty input strings, the spec doesn't require that. Curiously you're not ignoring null input strings.
Using a string as accumulator leads to quadratic runtime since it has to create a new string which contains all current data for each append.

Use StringBuilder.Append in Add instead. Don't return a string from Add, else you lose the performance advantage. Call stringBuilder.ToString() in your ToString operation. This has linear runtime.
You're returning null if no value has ever been added. I'd expect the empty string instead.

I don't know what they meant by calling your code "not detailed enough". You could add documentation for corner cases, possibly in the form of unit tests. For my observations 3 and 5 it's not clear if your code is behaving like you intended. Documentation and/or unit tests would have clarified your intent.


Function to ensure that at least one choice is selected First here is my settings object below. insight, spike and momentum are binded to 3 checkboxes in the markup. The objective here is to prevent the user from deselecting all choices, 1 choice must remain selected.

var settings = {
    user_id            : 0,
    insight            : true,
    spike              : true,
    momentum           : true,
    all_tickers        : true,
    errorMsg           : false,
    port_tickers       : [],
    fav_tags           : [],
    sensitivity        : 'medium',
    email_notification : true
};

So what I'm doing below is I create an Array with just the 3 keys from the settings object I want. Next I filter that array down to only the keys that are set to true. Next if the checkbox model is the same as the last item in the trueFilters Array I can then send back errorMsg = true.

function updateFilters(type) {
    settings[type] = !settings[type];

    // Create Array of filters that are true
    var filterKeys = _.map(settings, function(filter, key) {
        if (key === 'insight' || key === 'spike' || key === 'momentum') {
            if (filter) {
                return key;
            } else {
                return null;
            }
        } else {
            return null;
        }
    });

    // Remove any filters that are null/false
    var trueFilters = _.remove(filterKeys, function(n) {
        return n != null;
    });

    // If this filter is the last, prevent user from unselecting
    if (trueFilters.length === 0) {
        settings[type] = !settings[type];
        settings.errorMsg = true;
    }
}

if (key === 'insight' || key === 'spike' || key === 'momentum') {

Instead of looping through and checking these specific keys using an if, why not just create an array with the keys you're interested in and loop through that?

var filterKeys = ['insight', 'spike', 'momentum'];

Running on this, you can easily use map to gather the values, filter to reduce to only those that are true. Then checking if it's the last true filter will just be a matter of checking if what remains from a filter is an array with 1 as length.

Additionally, this function can be made so that it doesn't introduce side-effects or reduces the surface area of a side-effect. You can simply split off the logic to another function and return a boolean, while leaving the logic with side-effects (one that alters settings) in the caller.

function isLastFilter(settings) {
  var filters = ['insight', 'spike', 'momentum'];

  return filters.map(filter => settings[filter])
                .filter(value => value === true)
                .length === 1;
}

function updateFilters(type) {
  var shouldUpdate  = !isLastFilter(settings);
  settings[type]    = shouldUpdate ? settings[type] : !settings[type];
  settings.errorMsg = !shouldUpdate;
}

On other things, settings.errorMsg shouldn't be part of the data. It's a computation of other settings. In this case, it's derived from a state where there's only one filter present. The problem here is that updateFilters is essentially a "sync" function, syncing settings.errorMsg to the state of the other settings. Lose this, and you'll get an invalid state.

Drop settings.errorMsg. If you're using an ng-if or something to toggle the error in the UI, it should be something like ng-if="isLastFilter(settings)".


LeetCode #494: Target Sum (Python) Below is my solution to LC #494: Target Sum (given a list of numbers and a target integer, find out how many different ways the numbers can be subtracted from the total sum to result in the target sum).

There's one very common pattern in Python here that I question, and it's the use of for num in nums[1:]:. Iterating over nums[1:] is very explicit and readable, but it results in the creation of a whole new array when that really isn't our intention. That also means additional wasted time and wasted memory.

I used to always do for i in range(1, len(nums)): in these situations, but I see most other people using nums[1:]. Would love to hear thoughts on that.

And if there's a cleaner way to write this without having to initialize the counts hash from nums[0] separately from the body of the loop, that'd be great too. I couldn't think of a cleaner way.

class Solution:

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        counts = {nums[0]: 1, -nums[0]: 1}
        if nums[0] == 0:
            counts[0] += 1
        for num in nums[1:]:
            keys = list(counts)
            new = {}
            for key in keys:
                if key + num not in new:
                    new[key + num] = 0
                if key - num not in new:
                    new[key - num] = 0
                new[key + num] += counts[key]
                new[key - num] += counts[key]
            counts = new
        return counts[S] if S in counts else 0
```

for num in nums[1:] is the prefered way to iterate over a partition of an array; if you are worried about performance, it actually is faster, because accessing by index is more expensive in python than copying then iterating values (you can play with snippets of timeit to verify that claim, but I'm fairly sure of that - accessing by index in python involves way more checks and operations than it does in a language like C).

The performance issue with your program, if there is one, isn't there. The copy is just done once in the outter loop, and since it is repeated by num your inner loop is way more costy. Mind this: since every iteration can in the worst case double the number of items in keys, your program is actually of complexity O(2^n) where n is the array length.

In a matter of using more efficient structures you can also use Counter from collections that saves a bit of verbosity (it has zero as default value) and computation time (it is optimized C structure).

Without optimizing the algorithm, which I believe is part of the challenge :

from collections import Counter

class Solution:

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        counts = Counter()
        counts[-nums[0]] += 1
        counts[nums[0]] += 1
        for num in nums[1:]:
            new = Counter()
            for key in counts.keys():
                new[key + num] += counts[key]
                new[key - num] += counts[key]
            counts = new
        return counts[S]


Unsafe collection which allows immutable access while also allowing push() To get myself used to writing unsafe code, I wrote a collection which allows the user to keep immutable references to the elements of a vector while still being able to add new elements to it.

I would like to know if there is either a security problem with this code, an already implemented better alternative or some possible improvements in general (readability / performance).

pub struct UnsafeHolder<T> {
    items: Vec<Box<(T,String)>> // the vector contains Boxes, due to the fact that
                                // vectors can reallocate when adding elements
                                // which would end up creating dangling pointers
}

impl<T> UnsafeHolder<T> {
    pub fn new() -> Self {
        UnsafeHolder {
            items: vec![],
        }
    }

    // this method pretends to be immutable while actually adding
    // elements to the vector, this allows for continuous reference to
    // previous elements
    pub fn add_element(&self, element: T, key: String) {
        if !(self.items.iter().any( |i| i.1 == key)) {
            let mut items = unsafe {change_mut(&(self.items))};
            items.push(Box::new((element,key)));
        }
    }

    pub fn get_element(&self, key: &str) -> Option<&T> {
        if let Some(return_val) = self.items.iter().find(|i| i.1 == key) {
            Some(&return_val.0)
        }
        else {
            None
        }
    }

    pub fn clear(&mut self) {
        self.items = vec![];
    }
}

// this is used to change '&self' to '&mut self' to avoid the borrow checker
unsafe fn change_mut<T>(x: &T) -> &mut T {
    &mut *(x as *const T as *mut T)
}

This is the whole module, meaning that there should be no other ways than these 4 methods to interact with UnsafeHolder.

There is currently a problem due to the fact that items can be changed by multiple threads at once, resulting in an error.

Here is a link to the most recent version on playground.

Safety First

Unfortunately, programming in unsafe Rust requires respecting a number of rules; and you have broken at least one here.

Rust memory safety is based on the principle of Aliasing XOR Mutability, which is enforced as much as possible at compile-time for obvious performance reasons. When you wish to shift the responsibility from compile-time to run-time, you need to inform the compiler about it at the type level, lest it infers properties about the code that do not hold.

For interior mutability, use UnsafeCell.

This is the basic block that is used by all abstractions which defer the enforcement of the principle to run-time. For example, here is AtomicBool:

#[cfg(target_has_atomic = "8")]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct AtomicBool {
    v: UnsafeCell<u8>,
}

Thus, your type should be:

pub struct UnsafeHolder<T> {
    items: UnsafeCell<Vec<Box<(T,String)>>>,
}

Clean-up

UnsafeCell comes with a get method: UnsafeCell::get(&self) -> *mut T, and thus your change_mut function is unnecessary:

pub fn add_element(&self, element: T, key: String) {
    if !unsafe { & *self.items.get() }.iter().any(|i| i.1 == key) {
        let items = unsafe { &mut *self.items.get() };
        items.push(Box::new((element, key)));
    }
}

Nits and bits

Your add_element method should indicate when insertion fails; silent failures make programs harder to debug.

It seems strange to me to pass the element before the key; most APIs seem to do the reverse so I would advise following in their steps.

The complexity of your look-up is O(N), so that inserting repeatedly has O(N2) complexity; if you were sorting by key look-up could be O(log N) instead, and repeated insertion O(N log N).

I recommend avoiding unnecessary parentheses (such as in if !(...)); they clutter the code for no obvious gain.

Final Word

If you wish to venture into the world of unsafe, I recommend reading the Nomicon. Until Rust gets official unsafe semantics, it is probably the best reference about the dos and don'ts.


Binary Search implemented in C++ This is my implementation of a recursive binary search in C++. I'm still a newbie at C++ so:

Have I used any bad practices?
How could the code be improved upon in terms of efficiency?
Could recursion cause a stack overflow error, and if so how can I avoid this?

Criticism is welcome and appreciated!

#include<iostream>
#include<sstream>
#include<vector>

template <typename T>
void outputVector(std::vector<T> input){
    std::cout << "[";
    for(int i = 0; i < input.size(); i++){
        std::cout << input[i];
        if(i != input.size()-1){
            std::cout << ", ";
        }
    }
    std::cout << "]\n";
}

int binarySearch(std::vector<double> input, double target, int startIndex = 0){
    if(input.size() < 2){
        //std::cout << "Closest match found\n";
        return startIndex;
    }

    int middleIndex = int(input.size())/2;
    double middle = input[middleIndex];

    if(target == middle){
        return middleIndex + startIndex;
    }
    else if(target < middle){
        std::vector<double>::const_iterator begin = input.begin();
        std::vector<double>::const_iterator last = input.begin() + middleIndex;
        std::vector<double> firstHalf(begin, last);
        //std::cout << "First Half: ";
        //outputVector(firstHalf);
        return binarySearch(firstHalf, target, startIndex);
    }
    else if(target > middle){
        std::vector<double>::const_iterator begin = input.begin() + middleIndex + 1;
        std::vector<double>::const_iterator last = input.begin() + input.size();
        std::vector<double> secondHalf(begin, last);
        //std::cout << "Second Half: ";
        //outputVector(secondHalf);
        return binarySearch(secondHalf, target, startIndex+middleIndex+1);
    }
    else{
        return -1;
    }
}

std::vector<double> doubleVectorInput(){
    std::string inputString;
    getline(std::cin, inputString);
    std::vector<double> array;
    std::istringstream iss(inputString);
    float val;
    while(iss >> val){
        array.push_back(val);
    }
    return array;
}

int main(){
    double target;
    std::cout << "Vector to search: ";
    std::vector<double> input = doubleVectorInput();
    std::cout << "Target: "; std::cin >> target;
    std::cout << "Target index: " << binarySearch(input, target) << "\n";
    return 0;
}

Thank you.

Space Complexity

This is quite inefficient in terms of the storage space it uses.

Assuming the bisection works as we'd hope, and the vector is cut exactly in half every time, the recursive call copies half the input vector. If, for example, we started with an array of a million items, the first recursive call will copy half a million items. The second recursive call will copy a quarter of a million items.

Since the first call also passed the input array by value, we expect that our search of one million items ends up copying about two million items (in addition to the original vector the user passed).

Time Complexity

Copying those items takes a fair amount of time as well. To be more specific, it takes linear time.

Summary

We normally expect a binary search to have complexity of about \$O(log N)\$, and only descend to \$O(N)\$ in relatively rare worst cases. In this case, we get \$O(N)\$ in about the best case, and \$O(N^2)\$ in the bad cases.

This violates the normal expectations of a binary search badly enough that it effectively only barely qualifies as a binary search at all. In many cases, we can expect its performance to be substantially worse than a simple linear search.

Recommendation

You really don't want to pass the vector by value. Either pass it by reference, along with a pair of indexes into the vector giving the current upper and lower bounds of the part you want to search, or else pass a pair of iterators (there are probably other options as well, but in any case you want to pass an indication of the data to search rather than copying all the data you're going to search).

There are other parts of the code that could use changing as well, but that set of changes is likely to render many (most?) of them obsolete anyway, so I'm not going to get into other areas for now.


100 gunmen in a circle kill next person I am very happy because I solved this problem with very little code:

"""

    100 people are standing in a circle with gun in their hands.
    1 kills 2, 3 kills 4, 5 kills 6 and so on till we are
    left with only one person. Who will be the last person alive?
    Write code to implement this ##efficiently.## <-[ Python is not efficient]

"""

persons = list(range(1,101)) # The question asks 1-indexing

while len(persons) > 1:
    for index, person in enumerate(persons):
        del persons[(index + 1) % len(persons)]

print(persons)

1. Encapsulate

Writing code at the top level of a module makes it hard to test the code and hard to measure its performance. It's best to encapsulate code in a function. Accordingly, I'd write:

def survivor(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        for index, _ in enumerate(persons):
            del persons[(index + 1) % len(persons)]
    return persons[0]

(The variable person is not used in the body of the for loop; it's convential to write _ for such variables, and that's what I've done here.)

2. The meaning of efficiency

Is this code "efficient" as the question asks? Normally in computing we use "efficient" to mean algorithmic efficiency: that is, the rate at which the resources used by the program grow as a function of the input, usually expressed in big-O notation.

The question says, "Python is not efficient", but according to the usual view of efficiency, the programming language does not matter: efficiency is a property of the algorithm, not of the language it's implemented in.

3. It's accidentally quadratic

What's the runtime of the survivor function, expressed as a function of \$ n \$? Well, looking at the time complexity page on the Python Wiki, we can see that the del operation on a list takes \$ O(n) \$ where \$ n \$ is the length of the list, and this is executed once for each person who is killed, resulting in an overall runtime of \$ O(n^2) \$.

It's possible to check this experimentally:

>>> t = 1
>>> for i in range(8, 17):
...     t, u = timeit(lambda:survivor(2**i), number=1), t
...     print('{:6d} {:.6f} {:.2f}'.format(2**i, t, t / u))
...
   256 0.000138 0.00
   512 0.000318 2.31
  1024 0.000560 1.76
  2048 0.001363 2.43
  4096 0.006631 4.87
  8192 0.030330 4.57
 16384 0.132857 4.38
 32768 0.534205 4.02
 65536 2.134860 4.00

You can see that for each doubling of n, the runtime increases by roughly four times, which is what we expect for an \$ O(n^2) \$ algorithm.

4. Making it linear

How can we speed this up? Well, we could avoid the expensive del operation by making a list of the survivors, instead of deleting the deceased. Consider a single trip around the circular firing squad. If there are an even number of people remaining, then the people with indexes 0, 2, 4, and so on, survive. But if there are an odd number of people remaining, then the last survivor shoots the person with index 0, so the survivors are the people with indexes 2, 4, and so on. Putting this into code form:

def survivor2(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
    return persons[0]

(You could shorten this, if you liked, using an expression like persons[(len(persons) % 2) * 2::2], but I don't think the small reduction in code length is worth the loss of clarity.)

Let's check that this is correct, by comparing the results with the original implementation:

>>> all(survivor(i) == survivor2(i) for i in range(1, 1000))
True

Notice how useful it is for testing that we have the code organized into functions.

Now, what's the runtime of survivor2? Again, looking at the time complexity page on the Python Wiki, we can see that the "get slice" operation takes time \$ O(k) \$ where \$ k \$ is the number of items in the slice. In this case each slice is half the length of persons, so the runtime is $$ O\left({n \over 2}\right) + O\left({n \over 4}\right) + O\left({n \over 8}\right) + \dots $$ which is \$ O(n) \$. Again, we can check that experimentally:

>>> t = 1
>>> for i in range(8, 25):
...     t, u = timeit(lambda:survivor2(2**i), number=1), t
...     print('{:8d} {:8.6f} {:.2f}'.format(2**i, t, t / u))
...
     256 0.000034 0.00
     512 0.000048 1.40
    1024 0.000087 1.79
    2048 0.000142 1.63
    4096 0.000300 2.12
    8192 0.000573 1.91
   16384 0.001227 2.14
   32768 0.002628 2.14
   65536 0.006003 2.28
  131072 0.017954 2.99
  262144 0.043873 2.44
  524288 0.094669 2.16
 1048576 0.180889 1.91
 2097152 0.364302 2.01
 4194304 0.743028 2.04
 8388608 1.497255 2.02
16777216 3.094121 2.07

Now, for each doubling of n, the runtime increases by roughly two times, which is what we expect for an \$ O(n) \$ algorithm.

5. Making it polylogarithmic

Can we do even better than this? Let's look at who the survivors actually are after each trip around the firing squad:

from pprint import pprint

def survivors(n):
    """Print survivors after each round of circular firing squad with n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
        pprint(persons, compact=True)

>>> survivors(100)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81,
 83, 85, 87, 89, 91, 93, 95, 97, 99]
[1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77,
 81, 85, 89, 93, 97]
[9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97]
[9, 25, 41, 57, 73, 89]
[9, 41, 73]
[73]

After each round, the gap between the survivors doubles. So after one round, the survivors are every 2nd person; after two rounds, every 4th person, after three rounds, every 8th person, and so on. When there are an even number of people, the first person remains the first survivor in the next round. But when there are an odd number of people, the third person becomes the first survivor in the next round.

So to solve this problem, we don't need to remember all the survivors, we only need to remember the first survivor, the gap between survivors, and the total number of survivors. Like this:

def survivor3(n):
    """Return the survivor of a circular firing squad of n people."""
    first = 1
    gap = 1
    while n > 1:
        gap *= 2
        n, odd = divmod(n, 2)
        if odd:
            first += gap
    return first

Once again, we should check that this is correct:

>>> all(survivor(i) == survivor3(i) for i in range(1, 1000))
True

How fast is this? Here, each time round the loop we just have some arithmetic operations on numbers of size no more than \$ n \$, taking \$ O(\log n) \$, and each time around the loop we divide the number of survivors by two, so the loop executes \$ O(\log n) \$ times, for an overall runtime of \$ O((\log n)^2) \$.

>>> t = 0
>>> for i in range(8, 60, 4):
...     t, u = timeit(lambda:survivor3(2**i), number=1), t
...     print('{:20d} {:8.6f} {:.6f}'.format(2**i, t, t - u))
...
                 256 0.000014 0.000014
                4096 0.000012 -0.000001
               65536 0.000013 0.000001
             1048576 0.000015 0.000002
            16777216 0.000016 0.000002
           268435456 0.000018 0.000002
          4294967296 0.000022 0.000003
         68719476736 0.000030 0.000008
       1099511627776 0.000026 -0.000003
      17592186044416 0.000027 0.000001
     281474976710656 0.000031 0.000003
    4503599627370496 0.000032 0.000001
   72057594037927936 0.000035 0.000003

You can see that for each increase of n by a factor of 16, the runtime increases by a roughly constant amount, which is what we expect for a polylogarithmic algorithm.

Notice that the graph shows the runtime scaling roughly proportionally to \$ \log n \$ and not to \$ (\log n)^2 \$. That's because the values of \$ n \$ are small (less than \$ 2^{64} \$) and so in this range the arithmetic operations are effectively \$ O(1) \$. We'd have to use much larger values of \$ n \$ to show the asymptotic behaviour.

6. Further reading

This problem is (a simple case of) the well-known Josephus problem.