Reverse int within the 32-bit signed integer range: \$[−2^{31}, 2^{31} − 1]\$ Optimized LeetCode Problem

  Reverse digits of a 32-bit signed integer. When the reversed integer overflows return 0.

Feedback

Optimized from beta code in the original question here. Based on this LeetCode problem.. I'm trying to come up with a good approach that just math operations to iterate a serious of digits using division, almost treating the int like a stack popping using modulus, and pushing using multiplication.

#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>

class Solution
{
    public:
        int reverse(int i) {

            if(i > INT_MAX || i < INT_MIN) {
                return 0;
            }
            int sign = 1;
            if(i < 0) {
                sign = -1;
                i = i*sign;
            }

            int reversed = 0;
            int pop = 0;

            while(i > 0) {
                pop = i % 10;
                reversed = reversed*10 + pop;
                i /= 10;
            }

            std::cout << reversed << '\n';

            return reversed*sign;
        }
};

int main()
{
    Solution s;

    assert(s.reverse(1) == 1);
    assert(s.reverse(0) == 0);
    assert(s.reverse(123) == 321);
    assert(s.reverse(120) == 21);
    assert(s.reverse(-123) == -321);
    assert(s.reverse(1207) == 7021);
    assert(s.reverse(1534236469) == 0);
    assert(s.reverse(-2147483412) == -2143847412);
}

Unused header
We use nothing from <cmath>, so it need not be included.
This should be a function, not a class
Putting all code into a class suggests you have a background in Java or similar.
In C++, we can (and should) use ordinary functions for operations that are mathematically functions.  In this case, we have a pure function: it has no state, and should always give the same result for any given input.
If it's part of your program requirements that it must provide this (unhelpfully-named) class, then comment that.  I'd recommend that you still write a plain function, and simply provide an adapter to conform to the requirements:
int reverse_decimal_digits(int i);

class Solution
{
    public:
        int reverse(int i) { return reverse_decimal_digits(i); }
}

Choice of data type
If we're processing a 32-bit integer, then we should be using std::int32_t.  Plain int isn't necessarily large enough (it can be any size from 16 bits upwards).
Incorrect test
Given int i, then i > INT_MAX || i < INT_MIN is false by definition.  The requirement you quote is (my emphasis):

When the reversed integer overflows, return 0.

Not all integers have a negative
Beware of overflow here:

        if(i < 0) {
            sign = -1;
            i = i*sign;
        }

On 2s-complement systems, -1 * INT_MIN is undefined.
It turns out that we don't need this step, as in modern C++, the % operator can be used predictably with negative numbers to our advantage (see my modified code, below).
Don't do I/O from a pure function
I guess this is some leftover debugging that should have been removed:

        std::cout << reversed << '\n';

Additional tests
It's good that you've included some unit tests - I wish more people would do that!
Do think about which values to test.  Your choice agrees with mine somewhat, but diverges later:

0, 1 and -1 for the three simplest cases.
positive and negative two-digit numbers (e.g. 12 and -23).
smallest and largest allowable input (INT32_MIN and INT32_MAX).
smallest and largest allowable result, and the first overflow in each direction in first and last digits (±1463847412, ±1463847413,  ±1563847412).

Don't be tempted to over-test.  Tests need to be maintained, too, so try to limit the tests to those that exercise the limits within the implementation.
Minor improvements
The scope of pop can be reduced to within the loop.  And perhaps a better name would be digit?
noexcept and constexpr
Can we annotate the function with noexcept and constexpr?
Future
Should the number base be hard-coded to 10?  Perhaps there's a use for a reverser that works in arbitrary bases.  Certainly, base-16 is convenient for testing.

Modified code
I've used GoogleTest rather than plain C assert(), so as to get better messages when a test fails, but any testing method is fine.
#include <cstdint>

constexpr std::int32_t
reverse_digits(std::int32_t i, int base = 10) noexcept
{
    std::int32_t reversed = 0;
    const bool negative = i < 0;

    while (negative ? i <= -base : i >= base) {
        auto const digit = i % base; // negative if i < 0
        reversed = reversed * base + digit;
        i /= base;
    }

    // final digit may cause overflow
    const bool overflow =
        negative
        ? (reversed < (INT32_MIN - i) / base)
        : (reversed > (INT32_MAX - i) / base);
    if (overflow) {
        return 0;
    }

    return reversed * base + i;
}

#include <gtest/gtest.h>

TEST(Reverse, decimal)
{
    EXPECT_EQ(0, reverse_digits(0));
    EXPECT_EQ(1, reverse_digits(1));
    EXPECT_EQ(-1, reverse_digits(-1));

    EXPECT_EQ(21, reverse_digits(12));
    EXPECT_EQ(-32, reverse_digits(-23));

    EXPECT_EQ(0, reverse_digits(INT32_MIN));
    EXPECT_EQ(0, reverse_digits(INT32_MAX));

    EXPECT_EQ(2147483641, reverse_digits(1463847412));
    EXPECT_EQ(0, reverse_digits(1463847413));
    EXPECT_EQ(0, reverse_digits(1563847412));

    EXPECT_EQ(-2147483641, reverse_digits(-1463847412));
    EXPECT_EQ(0, reverse_digits(-1463847413));
    EXPECT_EQ(0, reverse_digits(-1563847412));
}

TEST(Reverse, hexadecimal)
{
    EXPECT_EQ(0x7ffffff7, reverse_digits(0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(0x10000008, 16));

    EXPECT_EQ(-0x7ffffff7, reverse_digits(-0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(-0x10000008, 16));
}


Check if number is divisible by three and two Looks next nested if a little structure redundancy? Any better way for next nested if?
# !/usr/bin/python3

num = int(input("enter number"))
if num%2 == 0:
   if num%3 == 0:
      print ("Divisible by 3 and 2")
   else:
      print ("divisible by 2 not divisible by 3")
else:
   if num%3 == 0:
      print ("divisible by 3 not divisible by 2")
   else:
      print  ("not Divisible by 2 not divisible by 3")

Instead of checking for division by 2 and 3 separately twice, you can make use of the fact that:
$$ 2 * 3 = 6$$
num = int(input("enter number"))
if num % 6 == 0:
    print("Divisible by 3 and 2")
elif num % 3 == 0:
    print("divisible by 3 not divisible by 2")
elif num % 2 == 0:
    print("divisible by 2 not divisible by 3")
else:
    print("not Divisible by 2 not divisible by 3")

python pep8 suggests to use 4-whitespace nesting as indentation levels.

Use 4 spaces per indentation level.

If you have more numbers to check divisibility against, keep a set of the numbers for which num % x == 0, and print the factors at the end.


HackerRank New Year Chaos: arriving at a given list using neighbor swaps I am trying to solve the HackerRank New Year Chaos problem where the aim is as follows:

A vector of size n is having values [1,2,3,...,(n-1),n] with no repetition. A kth element can switch only with the (k-1)th element. An element can maximum switch 2 times with its predecessor.

Thus we can say that any kth element should find its place at minimum (k-2)th index

Now, The vector given to the below given function minimumBribes() is the unordered / unsorted one, and I need to find the minimum switched occurred to the sorted vector.

NOTE: If the any element makes more than 2 switches, only print "Too chaotic"

void minimumBribes(vector<int> q) {
  int count = 0;

  for (int p_number = 0; p_number < q.size() - 1; p_number++) {

    if ((p_number+1) != q[p_number]) {
      vector<int>::iterator it = find(q.begin(), q.end(), (p_number+1));
        int index = distance(q.begin(), it);

        for (; index > p_number; index--) {
          if (q[index - 1] - index > 2) {
            cout << "Too chaotic" << endl;
            return;
          } else {
            q[index] = q[index - 1];
            count++;
          }
        }

        q[p_number] = (p_number+1);
    }
  }

  cout << count << endl;
}

The above solution works. but fails for 2 testcases with timeout error.

How to bring down the run time here?

Good attempt, but unfortunately the nested loop brings the time complexity to O(n2). Keep in mind that .find performs a linear search on the vector, inspecting up to the entire array to find an element. We can arrive at a O(n) solution by exploiting the fact that no more than 2 swaps can be performed by any given element, which is a red flag in the problem statement that your solution ignores. In other words, we can transform the linear operation inside the array to constant time.

Here's the approach I used:

Start at the back of the array and move forward. For each element q[i] not in its original location, check only q[i-1] and q[i-2] to see if it moved to one of those locations. If the element is in q[i-1], then it must have used only one bribe. If at q[i-2], it must have taken two bribes to get there. Either way, perform an un-swap to return it to its original location. If it's not at either element, the array is "Too chaotic".

Let's try this algorithm on the input examples:

Example 1

initial state:
[2, 1, 5, 3, 4]

[2, 1, 5, 3, 4]
             ^-- This element should be a 5. Let's look for 5 at index 3 or 2.
[2, 1, 5, 3, 4]
       ^-------- Found 5 at index 2. It must have swapped twice; set `bribes = 2`.
[2, 1, 3, 4, 5]
             ^-- Put 5 where it belongs by undoing the swaps it made.

[2, 1, 3, 4, 5]
          ^-- Moving to the next element, we see 4 is OK.

[2, 1, 3, 4, 5]
       ^-- Moving to the next element, we see 3 is OK.

[2, 1, 3, 4, 5]
    ^-- Moving to the next element, this element should be 2.
[2, 1, 3, 4, 5]
 ^----- Found 2. It must have swapped once; set `bribes = 3`.
[1, 2, 3, 4, 5]
    ^-- Put 2 where it belongs by undoing the swap it made.

Outcome: 3 bribes in total must have happened.

Example 2

initial state:
[2, 5, 1, 3, 4]

[2, 5, 1, 3, 4]
             ^-- This element should be 5. Let's find 5.
[2, 5, 1, 3, 4]
          ^----- This element, q[i-1], is not 5.
[2, 5, 1, 3, 4]
       ^-------- This element, q[i-2], is not 5, either.

Outcome: Too chaotic! 5 must have used more than 2
         bribes to get any further than index 2.


Dao function using hibernate I'm just wondering if the following is the best way to write a dao function.  Should I get the entity manager before the transaction and close it after the transaction every time?  Should I write transactions inside a dao?

public void sendBack(Long requestId,String comments){
    EntityManager em = getEntityManager();
    em.getTransaction().begin();
    String update = "update CsRequestReceivers set activeInd = :activeInd,sendBackComments=:comments where requestId = :requestId and activeInd = :oldActiveInd";
    em.createQuery(update).setParameter("activeInd", 0l)
                          .setParameter("comments", comments)
                          .setParameter("requestId", requestId)
                          .setParameter("oldActiveInd", 1l)
                          .executeUpdate();
    em.getTransaction().commit();
    em.close();
}

It depends on your app context. If im writting a web app Id create a filter which would getEntityManager(), begin() the transaction, then add it to the request scope, .doFilter() and pass it to the dao in the constructor (at the controller, of course).

When it returns to the filter id commit(), or even rollback() if any exception happens.


Invoke only by a single thread I wrote a simple class in Python, which controls code invocation, in a multi-threaded environment, with the following logic:

The class' main method, named try_to_do, takes two function pointers as arguments: yes_we_can_fn and no_we_cannot_fn.

In any point in time, only a single thread can invoke code the function passed as yes_we_can_fn argument.

If a specific thread tries to invoke its code, but some other thread is already invoking its code, then the no_we_cannot_fn is invoked instead of yes_we_can_fn.

If there's an exception in the code being executed, it should raise to the calling context.

The code:

from threading import Lock

class MyController():
    def __init__(self):
        self.locker = Lock()
        self.is_active = False

    def try_to_do(self, yes_we_can_fn, no_we_cannot_fn):
        with self.locker:
            if self.is_active:
                we_can_do_it = False
            else:
                we_can_do_it = True
                self.is_active = True

        try:
            if we_can_do_it:
                yes_we_can_fn()
            else:
                no_we_cannot_fn()
        finally:
            if we_can_do_it:
                with self.locker:
                    self.is_active = False

Usage:

ctl = MyController()

def p1():
    from time import sleep
    print 'before sleep'
    sleep(2)
    print 'done'

def p2():
    print 'too busy, will try some other time'

ctl.try_to_do(p1, p2)

I'd like to get some reviews: thread safety (maybe I'm missing something?), coding style, etc.

You could avoid the is_active variable by using the lock in a non-blocking manner:

def try_to_do(self, yes_we_can_fn, no_we_cannot_fn):
    if self.locker.acquire(False):
        try:
            yes_we_can_fn()
        finally:
            self.locker.release()
    else:
        no_we_cannot_fn()


Optimized MySQL query with complex calculation I am trying to pick 3 providers with the highest calculated score based on my algorithm, to recommend them to a user.

The recommendation algorithm takes into account a few things. Most are static values, but the one that is dynamic is the physical distance from the user (based on lat/lng). Since each user's location is different, I can't cache the distance in the DB.

I also need to limit the results to a) providers in a certain category (the WHERE ... IN clause), and b) providers that the user has not already added (the WHERE ... NOT IN clause)

Finally I order by score descending limit 3. Here is the query I am running. {$algorithm} is just a complex equation, {$categories} is a comma-separated list

SELECT `id`,
    {$algorithhm} AS `score`
    FROM `provider`
    WHERE `id` IN (
        SELECT `provider_id`
        FROM `provider_categories`
        WHERE `category_id` IN ( {$categories} )
    )
    AND `id` NOT IN (
        SELECT `provider_id`
        FROM `users_provider`
        WHERE `user_id` = {$current_user->id}
    )
    ORDER BY `score` DESC
    LIMIT 3

I have indexes on every column name you see here. There are only about 13,000 provider records in the database, yet the query takes about .04 seconds on average, which seems pretty slow to me. Back when there were 1,500 providers, it only took .003 seconds. Since I'm hoping to one day have hundreds of thousands, obviously this is a growing concern.

What can I do to speed this query up?

EXPLAIN tells me this:

   type             table                 type             key    ref          rows    Extra
1  PRIMARY          provider              ALL              NULL   NULL         12880   Using where; using filesort
3  DEPENDENT SUBQ   users_provider        eq_ref           PRI    const, func  1       Using where; using index
2  DEPENDENT SUBQ   provider_categories   index_subquery   PRI    func         1       Using index; using where

Edit

One thought I had was to limit it to providers within an X mile radius. But since the dynamic part of the algorithm is the distance calculation, I would still need to calculate the distance for every provider up front, so that doesn't really help. Maybe instead of a circular radius, I could check within a square lat/lng boundary, since those columns are indexed and the distance wouldn't need to be calculated... just thinking out loud. The main problem with this is that the geocoordinate to mile conversion is very different near the equator vs. near the poles.

Think one problem is that you have no key that it is using on the provider table, hence it is checking every row.

Not tested the following but this might be faster. Uses the provider_categories table as the first one (on which you are limiting the number of rows with a keyed check) and from that joining to the provider table.

SELECT b.id,
    {$algorithhm} AS score
FROM provider_categories a
INNER JOIN provider b ON a.provider_id = b.id
LEFT OUTER JOIN users_provider c ON a.provider_id = c.provider_id AND user_id = {$current_user->id}
WHERE c.provider_id IS NULL AND a.category_id IN ( {$categories} )
ORDER BY score DESC
LIMIT 3


Generic user input obtainer Earlier today I answered Timetable viewer, where one of my recommendations was to make a get_input function.
However, this hasn't been the first time I've recommended making a bespoke get_input function.

This function should get user input, until it is valid. This may be any input, or any number in a specific range.
The arguments customize how it works, such as working with strings or integers.
The function should repeatedly prompt the user for specific input, until a valid input is entered.
In the case case of valid input we should return that data, so the end user can use it.

Since it's quite a common function, with a lot of uses, I decided to make a generic version of the function, that should cover most use cases.
I decided to make two functions, as strings don't need to be converted, however when changing to numbers, you'd have to duplicate a lot of arguments.

def build_input(
    prompt=None,
    *,
    errors=None,
    values=None,
    process=None,
    wanted=None,
    end=None
  ):
    prompt = prompt or ''
    process = process or (lambda v: v)
    errors = errors or tuple()
    if values is None:
        wanted = wanted or (lambda v: True)
    else:
        values = list(values)
        prompt += '[{}] '.format('/'.join(str(i) for i in values))
        wanted = wanted or (lambda v: v in values)
        values = set(values)

    if end is not None:
        prompt += end
    elif values:
        prompt += '\n> '

    def ask():
        while True:
            value = input(prompt)
            try:
                value = process(value)
            except errors:
                continue
            if wanted(value):
                return value
    return ask

def build_number_input(
    prompt=None,
    *,
    errors=ValueError,
    values=None,
    process=int,
    wanted=None,
    end=None
  ):
    return build_input(
        prompt,
        errors=errors,
        values=values,
        process=process,
        wanted=wanted,
        end=end
    )

I have a couple of concerns:

build_number_input spans 17 lines, for a function definition and a function call. Is there a better way to define this?
Are there a better way to style my function definitions? I think they may not be PEP8 compliant, but couldn't think of anything nicer to read.
Are there any common options that you think should be added?

Below are a couple of ways to use the above functions, and a sample run:

name_input = build_input('What is your name? ')
age_input = build_number_input('What is your age? ')
day_input = build_number_input('Day: ', values=[1, 2, 3, 4, 5])
again_input = build_input('Again? ', values='yn', process=lambda v:v.lower())

print('Hello, {}! You are {}.'.format(name_input(), age_input()))
print('You want day {}'.format(day_input()))
print('You {}want to go again.'.format('' if again_input() == 'y' else "don't "))

What is your name? Peilonrayz
What is your age? 20.5
What is your age? 20a
What is your age? 20
Hello, Peilonrayz! You are 20.
Day: [1/2/3/4/5]
> 6
Day: [1/2/3/4/5]
> 0
Day: [1/2/3/4/5]
> 55
Day: [1/2/3/4/5]
> five
Day: [1/2/3/4/5]
> 5
You want day 5
Again? [y/n]
> yeah
Again? [y/n]
> Nope?
Again? [y/n]
> N
You don't want to go again.

I do not like the functional approach of this, especially since you are "inheriting" the user_input by number_input.
Here's an object-oriented version:

#! /usr/bin/env python3

class UserInput:

    def __init__(self, prompt=None, *, errors=None, values=None, process=None,
                 wanted=None, default=None, end=None):
        self.prompt = prompt
        self.errors = errors
        self.values = values
        self.process = process
        self.wanted = wanted
        self.default = default
        self.end = end

    def __call__(self):
        return self.get()

    @property
    def prompt(self):
        """Returns the prompt."""
        prompt = self._prompt or ''

        if self.values:
            prompt += '[{}] '.format('/'.join(str(i) for i in self.values))

        if self.end is not None:
            prompt += self.end
        elif self.values:
            prompt += '\n> '

        return prompt

    @prompt.setter
    def prompt(self, prompt):
        self._prompt = prompt

    @property
    def errors(self):
        return self._errors or tuple()

    @errors.setter
    def errors(self, errors):
        self._errors = errors

    @property
    def values(self):
        return self._values

    @values.setter
    def values(self, values):
        self._values = set(values) if values is not None else None

    @property
    def process(self):
        return self._process or (lambda v: v)

    @process.setter
    def process(self, process):
        self._process = process

    @property
    def wanted(self):
        """Returns the wanted callback."""
        if self._wanted:
            return self._wanted
        elif self.values is None:
            return lambda _: True

        return lambda value: value in self.values

    @wanted.setter
    def wanted(self, wanted):
        self._wanted = wanted

    def get(self):
        """Retrieves the user input."""
        while True:
            try:
                value = input(self.prompt)
            except (EOFError, KeyboardInterrupt):
                if self.default is not None:
                    return self.default

                raise

            try:
                value = self.process(value)
            except self.errors:
                continue

            if self.wanted(value):
                return value

class NumberInput(UserInput):

    def __init__(self, prompt=None, *, errors=ValueError, values=None,
                 process=int, wanted=None, end=None):
        super().__init__(
            prompt, errors=errors, values=values, process=process,
            wanted=wanted, end=end)

def main():

    name_input = UserInput('What is your name? ')
    age_input = NumberInput('What is your age? ')
    day_input = NumberInput('Day: ', values=[1, 2, 3, 4, 5])
    again_input = UserInput('Again? ', values='yn', process=lambda v:v.lower())

    print('Hello, {}! You are {}.'.format(name_input(), age_input()))
    print('You want day {}'.format(day_input()))
    print('You {}want to go again.'.format('' if again_input() == 'y' else "don't "))

if __name__ == '__main__':
    main()

I also added an additional keyword argument default the value of which will be returned on KeyboardInterrupts and EOFErrors (which occur on pressing [Ctrl]+[D]) iff specified.

Regarding the function of the code itself, I think that it is trying to be a jack-of-all-trades-device and doing a bad job at it while violating the YAGNI principle.
User input is highly variable and dynamic. If you think of a simple yes/no question where yes should be default (if one just hits enter) and the prompt should highlight the default value like in the pacman prompt below, this is really hard to implement using your functions (or classes).

$ LANG=en_US sudo pacman -S kate
resolving dependencies...
:: There are 2 providers available for phonon-qt5-backend:
:: Repository extra
   1) phonon-qt5-gstreamer  2) phonon-qt5-vlc

Enter a number (default=1):   # Just hit [Return] here.
looking for conflicting packages...
warning: dependency cycle detected:
warning: phonon-qt5-gstreamer will be installed before its phonon-qt5 dependency

Packages (43) attica-qt5-5.38.0-1  editorconfig-core-c-0.12.1-2  kactivities-5.38.0-1  karchive-5.38.0-1  kauth-5.38.0-1  kbookmarks-5.38.0-1  kcodecs-5.38.0-1  kcompletion-5.38.0-1  kconfig-5.38.0-1
              kconfigwidgets-5.38.0-1  kcoreaddons-5.38.0-1  kcrash-5.38.0-1  kdbusaddons-5.38.0-1  kglobalaccel-5.38.1-1  kguiaddons-5.38.0-1  ki18n-5.38.0-1  kiconthemes-5.38.0-1  kio-5.38.0-1
              kitemmodels-5.38.0-1  kitemviews-5.38.0-1  kjobwidgets-5.38.0-1  knewstuff-5.38.0-1  knotifications-5.38.0-1  kparts-5.38.0-1  kservice-5.38.0-1  ktexteditor-5.38.0-1  ktextwidgets-5.38.0-1
              kwallet-5.38.0-1  kwidgetsaddons-5.38.0-1  kwindowsystem-5.38.0-1  kxmlgui-5.38.0-1  libdbusmenu-qt5-0.9.3+16.04.20160218-1  media-player-info-22-2  phonon-qt5-4.9.1-4
              phonon-qt5-gstreamer-4.9.0-3  polkit-qt5-0.112.0+git20160226-1  qt5-multimedia-5.9.1-2  qt5-speech-5.9.1-2  solid-5.38.0-1  sonnet-5.38.0-1  syntax-highlighting-5.38.0-1  threadweaver-5.38.0-1
              kate-17.08.1-1

Total Download Size:    37.95 MiB
Total Installed Size:  146.67 MiB

:: Proceed with installation? [Y/n]  # Default option is capitalized.


Classic "100 doors" simulation in Clojure I read this question about the "100 Doors" puzzle, and thought that it would make for a good quick exercise.

I ended up with two implementations. The first is more straightforward and uses a vector to store the boolean state of each door.

This is quite slow though, and having a vector of true and falses seems off, so I decided to instead try making it use a set of open doors, and just toggle membership of the set. This is much faster, although the logic is a bit more complex.

I'd like just general feedback on anything that's here. The need for oneth-range is unfortunate (as is its name), and any suggestions to avoid its use would be nice. I know this can probably be solved entirely using simple math, but I'd like suggestions on the "manual" algorithm.

; Example of set-version usage and time
(let [n 5000]
  (time
    (find-open-doors-for n n)))
"Elapsed time: 939.315276 msecs"
=> (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900)

(ns irrelevant.hundred-doors-vec)

(defn- new-doors [n-doors]
  (vec (repeat n-doors false)))

(defn- multiple-of? [n mutliple]
  (zero? (rem n mutliple)))

(defn- oneth-range
  "Returns a range without 0. Max is inclusive."
  ([] (rest (range)))
  ([max] (rest (range (inc max)))))

(defn- toggle-doors
  "Toggles the state of every nth door."
  [doors every-n]
  (mapv #(if (multiple-of? % every-n)
           (not %2)
           %2)
        (oneth-range), doors))

(defn- toggle-doors-for [doors max-n]
  (reduce toggle-doors doors (oneth-range max-n)))

(defn find-open-doors-for
  "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."
  [n-doors n]
  (let [doors (new-doors n-doors)
        toggled (toggle-doors-for doors n)]

    (->> toggled
         (map vector (oneth-range))
         (filter second)
         (map first))))

(ns irrelevant.hundred-doors-set)

(defrecord Doors [open n-doors])

(defn- new-doors [n-doors]
  (->Doors #{} n-doors))

(defn- multiple-of? [n multiple]
  (zero? (rem n multiple)))

(defn- oneth-range
  "Returns a range without 0. Max is inclusive."
  ([] (rest (range)))
  ([max] (rest (range (inc max)))))

(defn- toggle-doors
  "Toggles the state of every nth door."
  [doors every-n]
  (update doors :open
    (fn [open]
      (reduce (fn [acc-set n]
                (cond
                  (not (multiple-of? n every-n)) acc-set
                  (open n) (disj acc-set n)
                  :else (conj acc-set n)))
              open
              (oneth-range (:n-doors doors))))))

(defn- toggle-doors-for [doors max-n]
  (reduce toggle-doors doors (oneth-range max-n)))

(defn find-open-doors-for
  "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."
  [n-doors n]
  (let [doors (new-doors n-doors)
        toggled (toggle-doors-for doors n)]

    (-> toggled
        (:open)
        (sort))))

My philosophy is "A fundamentally mutable problem requires a fundamentally mutable solution":

(def N 100)
(def bound (inc N))

(defn calc-doors []
  (verify (pos? N))
  (let [bound (inc N)
        doors (long-array bound 0) ]
    (doseq [step (range 1 bound)
            idx (range 0 bound step)]
      (aset-long doors idx
        (inc (aget doors idx))) )
     (vec doors)))

(dotest
  (let [doors (time (calc-doors))]
    (dotimes [i bound]
      (println (format "%5d %5d" i (nth doors i))))))

with result:

----------------------------------
   Clojure 1.9.0    Java 10.0.1
----------------------------------

Testing tst.demo.core
"Elapsed time: 0.498 msecs"

    0   100
    1     1
    2     2
    3     2
    4     3
    5     2
    6     4
    7     2
    8     4
    9     3
   10     4
   11     2
   12     6
   13     2
   14     4
   15     4
   16     5
   17     2
   18     6
   19     2
   20     6
   21     4
   22     4
   23     2
   24     8
   25     3
   26     4
   27     4
   28     6
   29     2
   30     8

Just noticed that you want the first N open doors:

(defn door-open?
  "Returns true if `door-idx` is open"
  [door-idx]
  (assert (pos? door-idx))
  (let [hits (atom 0)]
    (doseq [step (range 1 (inc door-idx))]
      (when (zero? (rem door-idx step))
        (swap! hits inc)))
    (odd? @hits)))

(defn first-n-open-doors
  "Return a vector of the first N open doors"
  [doors-wanted]
  (assert (pos? doors-wanted))
  (loop [idx       1
         open-idxs []]
    (let [next-idx       (inc idx)
          next-open-idxs (if (door-open? idx)
                           (conj open-idxs idx)
                           open-idxs)]
      (if (= doors-wanted (count next-open-idxs))
        next-open-idxs
        (recur next-idx next-open-idxs)))))

with result:

(first-n-open-doors 100) => [1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604 9801 10000]
"Elapsed time: 1279.926319 msecs"


Standard-layout tuple implementation I have written a simple (read: incomplete) tuple implementation that, AFAICT, does not violate the standard layout requirements. It's largely based on Nish's implementation, but I use a recursive hierarchy of nested members, rather than recursive inheritance. Unfortunately this approach necessitates recursion for element access.  But for my purposes I am willing to sacrifice compilation time for a predictable memory layout... my tuple stores elements in the "correct" order.

Aside from lengthy compilation times, are there any obvious flaws to this approach?

#include <cstddef>
#include <type_traits>

template <class... Ts>
struct tuple;

template <class T, class... Ts>
struct tuple<T, Ts...>
{
    T first;
    tuple<Ts...> rest;
};

template <class T>
struct tuple<T>
{
    T first;
};

namespace detail {

    template < ::std::size_t i, class T>
    struct tuple_element;

    template < ::std::size_t i, class T, class... Ts>
    struct tuple_element<i, tuple<T, Ts...> >
        : tuple_element<i - 1, tuple<Ts...> >
    {};

    template <class T, class... Ts>
    struct tuple_element<0, tuple<T, Ts...> >
    {
        using type = T;
    };

    template < ::std::size_t i>
    struct tuple_accessor
    {
        template <class... Ts>
        static inline typename tuple_element<i, tuple<Ts...> >::type & get (tuple<Ts...> & t)
        {
            return tuple_accessor<i - 1>::get(t.rest);
        }

        template <class... Ts>
        static inline const typename tuple_element<i, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
        {
            return tuple_accessor<i - 1>::get(t.rest);
        }
    };

    template <>
    struct tuple_accessor<0>
    {
        template <class... Ts>
        static inline typename tuple_element<0, tuple<Ts...> >::type & get (tuple<Ts...> & t)
        {
            return t.first;
        }

        template <class... Ts>
        static inline const typename tuple_element<0, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
        {
            return t.first;
        }
    };

    template <class T, class... Ts>
    struct tuple_builder
    {
        static inline void make (tuple<typename ::std::decay<T>::type, typename ::std::decay<Ts>::type...> & t, T && x, Ts &&... xs)
        {
            t.first = x;
            tuple_builder<Ts...>::make(t.rest, ::std::forward<Ts>(xs)...);
        }
    };

    template <class T>
    struct tuple_builder<T>
    {
        static inline void make (tuple<typename ::std::decay<T>::type> & t, T && x)
        {
            t.first = x;
        }
    };

} // namespace detail

template <class... Ts>
inline tuple<typename ::std::decay<Ts>::type...> make_tuple (Ts &&... x)
{
    tuple<typename ::std::decay<Ts>::type...> t;
    detail::tuple_builder<Ts...>::make(t, ::std::forward<Ts>(x)...);
    return t;
}

template < ::std::size_t i, class... Ts>
inline typename detail::tuple_element<i, tuple<Ts...> >::type & get (tuple<Ts...> & t)
{
    return detail::tuple_accessor<i>::get(t);
}

template < ::std::size_t i, class... Ts>
inline const typename detail::tuple_element<i, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
{
    return detail::tuple_accessor<i>::get(t);
}

static_assert(::std::is_standard_layout<tuple<bool, int, float, char, double, tuple<int, char> > >(), "Compiler is stupid");

For more context, see this

Minor issues:

You need to include <utility> for std::forward.
You don't support empty tuples. It's obviously not a huge problem, but adding one line

template <> struct tuple<> {};

is no great burden either.
You should be using std::forward for the assignments in the make functions:

t.first = std::forward<T>(x);

so move assignment is used when x is an rvalue reference.

Slightly bigger issue:

Having no constructors in tuple means that your tuple can never contain a type that is not default constructible. "Default construction followed by assignment" is inherently less efficient than value construction. I would write perfect forwarding constructors for the tuple specializations, something like:

template <class T, class... Ts>
struct tuple<T, Ts...>
{
    T first;
    tuple<Ts...> rest;

    tuple() = default;
    template <class U, class...Us, class=
      typename ::std::enable_if<
        !::std::is_base_of<
          tuple,
          typename ::std::decay<U>::type
        >::value
      >::type
    >
    tuple(U&& u, Us&&...tail) :
      first(::std::forward<U>(u)),
      rest(::std::forward<Us>(tail)...) {}
};

template <class T>
struct tuple<T>
{
    T first;

    tuple() = default;
    template <class U, class=
      typename ::std::enable_if<
        !::std::is_base_of<
          tuple,
          typename ::std::decay<U>::type
        >::value
      >::type
    >
    tuple(U&& u) :
      first(::std::forward<U>(u)) {}
};

(All that enable_if junk is to keep the perfect forwarding constructors from being used for copy/move construction from another tuple.) This allows make_tuple to become a one-liner:

return tuple<typename ::std::decay<Ts>::type...>(::std::forward<Ts>(x)...);

(Code demo with suggested changes and the now-unnecessary builder templates removed)


Standard deviation of hourly temperatures of 2 days It seems that when I program in Lisp my brain goes on auto pilot and I end up solving the problem somehow. I don't even think I just do and it works out.

That said, this is some horrible Lisp code that was hacked together in about 20 mins, just to see if I could do it.

The C++ program that this is based off was about 150 lines long, so doing it in about 59 lines of terrible code is neat.

The date is 50 lines and is structured like 2 dates and 48 doubles 1 for each hour:

3/14/2015
3/15/2015
32.12
12.23
34.12
.
.
56.12

(defun read-nth-line (file n &aux (line-number 0))
  "Read the nth line from a text file. The first line has the number 1"
  (assert (> n 0) (n))
  (with-open-file (stream file)
    (loop for line = (read-line stream nil nil)
          if (and (null line) (< line-number n))
            do (error "file ~a is too short, just ~a, not ~a lines long"
                      file line-number n)
          do (incf line-number)
          if (and line (= line-number n))
       do (return line))))

(defun arithmetic-average (samples)
  (/ (reduce #'+ samples)
     (length samples)))

(defun get-file (filename)
  (with-open-file (stream filename)
    (loop for line = (read-line stream nil)
          while line
       collect line)))

   ;; compute sDev
(defun standard-dev (colc)
  (let ((mean (arithmetic-average colc)))
    (sqrt (* (/ 1.0d0 (length colc))
         (reduce #'+ colc
             :key (lambda (x)
                (expt (- x mean) 2)))))))

(defun split-in-half (sequence)
  (let ((mid (ceiling (length sequence) 2)))
    (list (subseq sequence 0 mid)
            (subseq sequence mid nil))))

(defun parse-string-to-float (line)
  (with-input-from-string (s line)
    (loop
      :for num := (read s nil nil)
      :while num
      :collect num)))

(defun extract-float (line)
  "doc"
 (first (parse-string-to-float line)))

(defun process-file ()
  "print mean and standard deviation to terminal"
  (let* ((l1 (get-file "~/ClionProjects/project5withTemplates/twoday.txt"))
     (date1 (first l1))
     (date2 (second l1))
     (day1temps (mapcar #'extract-float (first (split-in-half (rest (rest l1))))))
     (day2temps (mapcar #'extract-float (second (split-in-half (rest (rest l1))))))
     (s-dev-day-1 (standard-dev day1temps))
     (s-dev-day-2 (standard-dev day2temps)))
    (print "date:")(print date1) (print "standard deviation:") (print s-dev-day-1)
    (print "date:")(print date2) (print "standard deviation:") (print s-dev-day-2)) nil)

You are doing fine, other than a few simple nitpicks.

You are not using read-nth-line (which is a crazy thing to do anyway), please drop it.

You should fix your indentation, it would make your code much easier to read.

You probably want to divide by N-1, not N, in standard-dev and you probably want to simplify the code there by dividing by N-1 instead of multiplying by the reciprocal; also expt is relatively expensive, so, if you were not i/o bound anyway, you might want to replace it with multiplication.

Function split-in-half should probably return multiple values instead of a list.

Global variable l1 should be local to process-file.

Function parse-string-to-float should probably be called parse-string-to-floats (it read the whole list).


Implementation of Vertex Similarity algorithm (Blondel's Similarity Measure) I am implementing the vertex similarity algorithm in this paper. The adjacency matrices I will be dealing with, however, will be very large, on the order of 30k vertices (I provided sample matrices in the main method).

The algorithm is to calculate S(k+1) as an iterative matrix. The algorithm is given on page 2 of the paper (listed as 114).

According to the paper, the implementation below is correct. What I want feedback on is memory efficiency, to not make new matrices as much as possible.

public class Matrix {
private final int M, N;
private final double[][] data;

public Matrix(int M, int N) {
    this.M = M;
    this.N = N;
    data = new double[M][N];
}

public Matrix(double[][] data) {
    M = data.length;
    N = data[0].length;
    this.data = new double[M][N];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
                this.data[i][j] = data[i][j];
}

public Matrix transpose() {
    Matrix A = new Matrix(N, M);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            A.data[j][i] = data[i][j];
    return A;
}

public Matrix plus(Matrix B) {
    Matrix A = this;
    assert B.M != A.M || B.N != A.N;
    Matrix C = new Matrix(M, N);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            C.data[i][j] = A.data[i][j] + B.data[i][j];
    return C;
}

public Matrix times(Matrix B) {
    Matrix A = this;
    assert A.N == B.M;
    Matrix C = new Matrix(A.M, B.N);
    for (int i = 0; i < C.M; i++)
        for (int j = 0; j < C.N; j++)
            for (int k = 0; k < A.N; k++)
                C.data[i][j] += (A.data[i][k] * B.data[k][j]);
    return C;
}

@Override
public String toString() {
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            s.append(data[i][j]).append(" ");
        }
        s.append("\n");
    }
    return s.toString();
}

public static void main(String[] args) {
    // Sample matrices
    double[][] a = {
            {0,1,0,1},
            {1,0,1,0},
            {0,1,0,0},
            {1,0,0,0}
    };
    double[][] b = {
            {0,0,1,1,0,0},
            {0,0,0,1,0,1},
            {1,0,0,0,1,1},
            {0,0,0,0,0,0},
            {0,0,0,0,0,0},
            {1,0,1,1,0,0}
    };
    // Xk is the iteration of the algorithm matrix.
    double[][] xk = new double[b.length][a[0].length];
    for (int i = 0; i < xk.length; i++) {
        for (int j = 0; j < xk[0].length; j++) {
            xk[i][j] = 1;
        }
    }
    Matrix X = new Matrix(a);
    Matrix Y = new Matrix(b);
    Matrix Sk = new Matrix(xk);
    int n = 10; // number of iterations of algorithm
    for (int i=0; i<n; i++) {
        // This is the actual algorithm.
        Matrix firstProduct = Y.times(Sk).times(X.transpose());
        Matrix secondProduct = Y.transpose().times(Sk).times(X);
        Matrix totalProduct = firstProduct.plus(secondProduct);
        double[][] data = totalProduct.transpose().data;
        Sk = new Matrix(normalizeByRows(data)).transpose();
        System.out.println(Sk);
        System.out.println("------------");
    }
    // This is to calculate the average value in Sk.
    double[][] data = Sk.data;
    double sum = 0.0;
    int count = 0;
    for (double[] j : data) {
        for (double l : j) {
            count++;
            sum += l;
        }
    }
    sum /= count;
    System.out.println(sum);
}

private static double[][] normalizeByRows(double[][] data) {
    for (int k=0; k<data.length; k++) {
        double[] row = data[k];
        double max = 0;
        for (double l : row) {
            max += l;
        }
        for (int l = 0; l < data[k].length; l++) {
            data[k][l] /= max;
        }
    }
    return data;
}
}

private final int M, N;

It's Java. Albeit M and N may get big, you should use camelcase (small initial letters) for non-constant fields. Maybe something like width and height? Or rows and colums, or m and n, if you insist.

public Matrix(double[][] data) {
    M = data.length;
    N = data[0].length;
    this.data = new double[M][N];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
                this.data[i][j] = data[i][j];
}

Either make the method non-public or check arguments, especially check that each row has the same length. Apart from this, the inner loop could be replaced by

this.data[i] = data[i].clone();

  What I want feedback on is memory efficiency, to not make new matrices as much as possible.

Matrix firstProduct = Y.times(Sk).times(X.transpose());

Here you're creating an new matrix, while a view of the original would do (albeit probably slower). You could instead define a timesTransposed operation and have the full speed without any allocations. That's pretty simple and you can test it nicely using the existing operations.

Matrix totalProduct = firstProduct.plus(secondProduct);

Here you can avoid allocations by implementing the equivalent of +=. It surely doesn't make you code more readable, but sometimes that's the price for efficiency.

An operation like *= could get pretty complicated for matrices (and is rather impossible for non-square matrices, so lets forget it).

    double[][] data = totalProduct.transpose().data;
    Sk = new Matrix(normalizeByRows(data)).transpose();

Here, you're refusing to use objects and I really can't why. normalizeByRows should be a method (either modifying an existing matrix or creating a new one; choose what you need, but be careful with naming).

// This is the actual algorithm.

So don't put it in main. Make a method, name it properly and save yourself that comment.


VLookup simulation: copying data from one sheet to another I tried to write a VLOOKUP in my macro but for some unknown reasons it didn't work (see my post on StackOverFlow for more info.

So I decided to do a macro which achieves the same result, but it takes about 20 sec to run. Any ideas on how I can improve its performance ?

What this macro is doing :

I have 2 worksheets in my workbook. Both have a column listing VINs + other info. What this macro is doing is a Vlookup from one sheet to the other one to retrieve some information when the same VIN is found.

Sub ReplacementVlookups()

'Delete Rows with no content
    Dim i As Integer
    i = 0
    Do
    i = i + 1
    Loop While Range("A" & i) <> ""
    Rows(i & ":" & Worksheets("All Time SMS Dump").Range("A" & Rows.Count).End(xlUp).Row).Delete (xlShiftUp)
Worksheets("All Time SMS Dump").Columns("G:G").NumberFormat = "General"
Worksheets("All Time SMS Dump").Columns("H:H").NumberFormat = "General"
'Store all Lookup values in a 1D array
Dim VLookupType As Integer
Dim j As Integer
Dim LastRow As Integer
Dim LastRowSF As Integer
Dim VINArrayAllTime As Variant
Dim VINArraySF As Variant
Dim ValuesCopied As Variant
Dim ValuesPasted As Variant
LastRow = Worksheets("All Time SMS Dump").Range("A" & Rows.Count).End(xlUp).Row
LastRowSF = Worksheets("Salesforce Dump").Range("A" & Rows.Count).End(xlUp).Row
VINArrayAllTime = Worksheets("All Time SMS Dump").Range("A2:A" & LastRow)
VINArraySF = Worksheets("Salesforce Dump").Range("C2:C" & LastRowSF)
For VLookupType = 1 To 3 ' I have 3 columns on which I want to apply the VLookup
    If VLookupType = 1 Then
        ValuesCopied = Worksheets("Salesforce Dump").Range("D2:D" & LastRowSF)
        ValuesPasted = Worksheets("All Time SMS Dump").Range("G2:G" & LastRow)
        'Do a VLOOKUP
        For i = 2 To LastRow
            For j = 2 To LastRowSF - 1
                If VINArrayAllTime(i - 1, 1) = VINArraySF(j - 1, 1) Then
                    ValuesPasted(i - 1, 1) = ValuesCopied(j - 1, 1)
                    Exit For
                End If
            Next j
        Next i

        Worksheets("All Time SMS Dump").Range("G2:G" & LastRow) = ValuesPasted
    ElseIf VLookupType = 2 Then
        ValuesCopied = Worksheets("Salesforce Dump").Range("E2:E" & LastRowSF)
        ValuesPasted = Worksheets("All Time SMS Dump").Range("H2:H" & LastRow)
        'Do a VLOOKUP
        For i = 2 To LastRow
            For j = 2 To LastRowSF - 1
                If VINArrayAllTime(i - 1, 1) = VINArraySF(j - 1, 1) Then
                    ValuesPasted(i - 1, 1) = ValuesCopied(j - 1, 1)
                    Exit For
                End If
            Next j
        Next i

        Worksheets("All Time SMS Dump").Range("H2:H" & LastRow) = ValuesPasted

    Else:
        ValuesCopied = Worksheets("Salesforce Dump").Range("F2:F" & LastRowSF)
        ValuesPasted = Worksheets("All Time SMS Dump").Range("I2:I" & LastRow)
        'Do a VLOOKUP
        For i = 2 To LastRow
            For j = 2 To LastRowSF - 1
                If VINArrayAllTime(i - 1, 1) = VINArraySF(j - 1, 1) Then
                    ValuesPasted(i - 1, 1) = ValuesCopied(j - 1, 1)
                    Exit For
                End If
            Next j
        Next i

        Worksheets("All Time SMS Dump").Range("I2:I" & LastRow) = ValuesPasted
    End If
Next VLookupType

End Sub

This was an interesting challenge - improve performance of arrays

But first, to cover the basics:

Option Explicit is missing - this statement fixes the most basic syntax issues
The range references are good overall, but lengthy and repetitive

The only one missing is on the 6th line Rows(... which deletes rows from active sheet

Indentation is inconsistent, and missing at the first level (Sub - End Sub)
The first loop doesn't work properly, and every execution it deletes the last row with data

For 10 rows i=11, but the .End(xlUp).Row is 10, and becomes Rows("11:10").Delete

'Delete Rows with no content
 Dim i As Integer
 i = 0
 Do
   i = i + 1
 Loop While Range("A" & i) <> ""
 Rows(i & ":" & Worksheets("All Time SMS Dump").Range("A" & Rows.Count).End(xlUp).Row).Delete (xlShiftUp)

In all For loops you have For i = 2 To... & For j = 2 To... then compare i - 1 = j - 1

Assigning .Range("D2:D" & LastRowSF) to array, first item in the array is D2 (index 1)

The main Sub defaults to public, but the Public keyword should be explicit

Most subs and functions should be made Private to modules unless they are utilities

On to Performance

I'm providing 3 versions for comparison (v1 - is your version with three For loops)

v2 - Code cleanup and optimization (three For loops)
v3 - Improve performance - change algorithm (one For loop)
v4 - Arrays and a dictionary (one For loop)

v2 - Code cleanup and optimization (three For loops)

Public Sub VinLookUpArr1()
    Dim wsAT As Worksheet, wsSF As Worksheet, valAT As Variant, valSF As Variant
    Dim lrAT As Long, lrSF As Long, vinAT As Variant, vinSF As Variant, t As Double

    t = Timer
    Set wsAT = ThisWorkbook.Worksheets("All Time SMS Dump")
    Set wsSF = ThisWorkbook.Worksheets("Salesforce Dump")

    lrAT = wsAT.Range("A" & Rows.Count).End(xlUp).Row
    lrSF = wsSF.Range("A" & Rows.Count).End(xlUp).Row

    vinAT = wsAT.Range("A2:A" & lrAT)
    vinSF = wsSF.Range("C2:C" & lrSF)

    wsAT.Rows(wsAT.Rows(1).End(xlDown).Row + 1 & ":" & lrAT + 1).Delete xlShiftUp
    wsSF.Rows(wsSF.Rows(1).End(xlDown).Row + 1 & ":" & lrSF + 1).Delete xlShiftUp
    wsAT.Columns("G:H").NumberFormat = "General"

    valAT = wsAT.Range("G2:G" & lrAT)
    valSF = wsSF.Range("D2:D" & lrSF)
    wsAT.Range("G2:G" & lrAT) = DoLookUpArr1(vinAT, vinSF, valAT, valSF)
    valAT = wsAT.Range("H2:H" & lrAT)
    valSF = wsSF.Range("E2:E" & lrSF)
    wsAT.Range("H2:H" & lrAT) = DoLookUpArr1(vinAT, vinSF, valAT, valSF)
    valAT = wsAT.Range("I2:I" & lrAT)
    valSF = wsSF.Range("F2:F" & lrSF)
    wsAT.Range("I2:I" & lrAT) = DoLookUpArr1(vinAT, vinSF, valAT, valSF)
    Debug.Print "lrAT: " & lrAT & "; lrSF: " & lrSF & "; Time: " & Format(Timer - t, "0.000")
End Sub

Private Function DoLookUpArr1(ByVal vinAT As Variant, ByVal vinSF As Variant, _
                              ByVal valAT As Variant, ByVal valSF As Variant) As Variant

    Dim rAT As Long, rSF As Long, lrSF As Long

    lrSF = UBound(valSF)
    For rAT = 1 To UBound(valAT)
        For rSF = 1 To lrSF
            If vinAT(rAT, 1) = vinSF(rSF, 1) Then
                valAT(rAT, 1) = valSF(rSF, 1)
                Exit For
            End If
        Next rSF
    Next rAT
    DoLookUpArr1 = valAT
End Function

v3 - Improve performance - change algorithm (one For loop)

This loops only once for all vLookups:

Public Sub VinLookUpArr2()
    Dim wsAT As Worksheet, wsSF As Worksheet, urAT As Variant, urSF As Variant
    Dim lrAT As Long, lrSF As Long, lcAT As Long, lcSF As Long, t As Double
    Dim rAT As Long, rSF As Long, map(1 To 2, 1 To 4) As Byte, i As Long

    t = Timer
    Set wsAT = ThisWorkbook.Worksheets("All Time SMS Dump")
    Set wsSF = ThisWorkbook.Worksheets("Salesforce Dump")

    map(1, 1) = 1:    map(2, 1) = 3        'A to C (VINs)
    map(1, 2) = 7:    map(2, 2) = 4        'G to D
    map(1, 3) = 8:    map(2, 3) = 5        'H to E
    map(1, 4) = 9:    map(2, 4) = 6        'I to F

    lrAT = wsAT.Cells(Rows.Count, 1).End(xlUp).Row              'lr = last row
    lrSF = wsSF.Cells(Rows.Count, 1).End(xlUp).Row
    lcAT = wsAT.Cells(1, Columns.Count).End(xlToLeft).Column    'lc = last col
    lcSF = wsSF.Cells(1, Columns.Count).End(xlToLeft).Column

    urAT = wsAT.Range(wsAT.Cells(1), wsAT.Cells(lrAT, lcAT))    'ur = used range
    urSF = wsSF.Range(wsSF.Cells(1), wsSF.Cells(lrSF, lcSF))

    For rAT = 2 To lrAT
        For rSF = 2 To lrSF
            If urAT(rAT, map(1, 1)) = urSF(rSF, map(2, 1)) Then
                For i = 2 To 4
                    urAT(rAT, map(1, i)) = urSF(rSF, map(2, i))
                Next
                Exit For
            End If
        Next
    Next
    wsAT.Range(wsAT.Cells(1), wsAT.Cells(lrAT, lcAT)) = urAT
    Debug.Print "lrAT: " & lrAT & "; lrSF: " & lrSF & "; Time: " & Format(Timer - t, "0.000")
End Sub

v4 - Arrays and a dictionary (one For loop)

The most important improvement is gained by the .Exists() method of the dictionary

Public Sub VinLookUpDictionary()
    Dim wsAT As Worksheet, wsSF As Worksheet, urAT As Variant, urSF As Variant
    Dim lrAT As Long, lrSF As Long, lcAT As Long, lcSF As Long, t As Double
    Dim rAT As Long, rSF As Long, map(1 To 2, 1 To 4) As Byte, i As Long, d As Dictionary
    t = Timer
    Set d = New Dictionary
    Set wsAT = ThisWorkbook.Worksheets("All Time SMS Dump")
    Set wsSF = ThisWorkbook.Worksheets("Salesforce Dump")
    map(1, 1) = 1:    map(2, 1) = 3        'A to C (VINs)
    map(1, 2) = 7:    map(2, 2) = 4        'G to D
    map(1, 3) = 8:    map(2, 3) = 5        'H to E
    map(1, 4) = 9:    map(2, 4) = 6        'I to F
    lrAT = wsAT.Cells(Rows.Count, 1).End(xlUp).Row              'lr = last row
    lrSF = wsSF.Cells(Rows.Count, 1).End(xlUp).Row
    lcAT = wsAT.Cells(1, Columns.Count).End(xlToLeft).Column    'lc = last col
    lcSF = wsSF.Cells(1, Columns.Count).End(xlToLeft).Column
    urAT = wsAT.Range(wsAT.Cells(1), wsAT.Cells(lrAT, lcAT))    'ur = used range
    urSF = wsSF.Range(wsSF.Cells(1), wsSF.Cells(lrSF, lcSF))
    For rSF = 2 To lrSF
        d(urSF(rSF, map(2, 1))) = vbNullString
    Next
    For rAT = 2 To lrAT
        For rSF = 2 To lrSF
            If d.Exists(urAT(rAT, map(1, 1))) Then
                For i = 2 To 4
                    urAT(rAT, map(1, i)) = urSF(rSF, map(2, i))
                Next
                Exit For
            End If
        Next
    Next
    wsAT.Range(wsAT.Cells(1), wsAT.Cells(lrAT, lcAT)) = urAT
    Debug.Print "lrAT: " & lrAT & "; lrSF: " & lrSF & "; Time: " & Format(Timer - t, "0.000")
End Sub

Results

Total Rows on sheet "All Time SMS Dump": 20,001
Total Rows on sheet "Salesforce Dump":   20,001

v1 = Time: 53.469 sec (arrays - 3 loops)
v2 = Time: 54.676 sec (arrays - 3 loops)
v3 = Time: 20.637 sec (arrays - 1 loop)
v4 = Time:  0.484 sec (arrays & dictionary - 1 loop)


A binary search solution to 3Sum I tried a binary solution to 3Sum problem in LeetCode:

  Given an array nums of \$n\$ integers, are there elements \$a\$, \$b\$, \$c\$ in nums such that \$a + b + c = 0\$? Find all unique triplets in the array which gives the sum of zero.

  Note:

  The solution set must not contain duplicate triplets.

  Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Ｍy plan: divide and conquer threeSum to

an iteration
and a two_Sum problem.
break two_Sum problem to

a loop
binary search

The complexity is: \$O(n^2\log{n})\$.

 class Solution:
    """
    Solve the problem by three module funtion
    threeSum
    two_sum
    bi_search
    """
    def __init__(self):
        self.triplets: List[List[int]] = []

    def threeSum(self, nums, target=0) -> List[List[int]]:
        """
        :type nums: List[int]
        :type target: int
        """
        nums.sort() #sort for skip duplicate and binary search

        if len(nums) < 3:
            return []

        i = 0
        while i < len(nums) - 2:
            complement = target - nums[i]

            self.two_sum(nums[i+1:], complement)
            i += 1 #increment the index
            while i < len(nums) -2 and nums[i] == nums[i-1]: #skip the duplicates, pass unique complement to next level.
                i += 1

        return self.triplets

    def two_sum(self, nums, target):
        """
        :type nums: List[int]
        :tppe target: int
        :rtype: List[List[int]]
        """
        # nums = sorted(nums) #temporarily for testing.
        if len(nums) < 2:
            return []

        i = 0
        while i < len(nums) -1:
            complement = target - nums[i]

            if self.bi_search(nums[i+1:], complement) != None:

                # 0 - target = threeSum's fixer
                self.triplets.append([0-target, nums[i], complement])
            i += 1

            while i < len(nums) and nums[i] == nums[i-1]:
                i += 1

    def bi_search(self, L, find) -> int:
        """
        :type L: List[int]
        :type find: int
        """
        if len(L) < 1: #terninating case
            return None
        else:
            mid = len(L) // 2
            if find == L[mid]:
                return find

            if find > L[mid]:
                upper_half = L[mid+1:]
                return self.bi_search(upper_half, find)
            if find < L[mid]:
                lower_half = L[:mid] #mid not mid-1
                return self.bi_search(lower_half, find)

I ran it but get the report

  Status: Time Limit Exceeded

Could you please give any hints to refactor?

Is binary search is an appropriate strategy?

Your bi_search() method is recursive.  It doesn’t have to be.  Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop.  Instead of if len(L) < 1:, use a while len(L) > 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call.

Better: don’t modify L at all, which involves copying a list of many numbers multiple times, a time consuming operation.  Instead, maintain a lo and hi index, and just update the indexes as you search.

Even better: use a built in binary search from import bisect.


Capitalize string except for conjunction words I am using the code below to capitalize words in a string. I do not want conjunction words capitalized, but always want the first character in the string to be capitalized no matter what the word is. Is this the most optimized way of accomplishing this? How could this be improved?

xText = queryForHeading
xTextSplit = split(xText, " ")

for each item in xTextSplit
    xWord = item
    if lcase(item) = "a" or lcase(item) = "an" or lcase(item) = "and" or lcase(item) = "as" or lcase(item) = "at" or lcase(item) = "but" or lcase(item) = "by" or lcase(item) = "en" or lcase(item) = "for" or lcase(item) = "if" or lcase(item) = "in" or lcase(item) = "is" or lcase(item) = "nor" or lcase(item) = "of" or lcase(item) = "on" or lcase(item) = "or" or lcase(item) = "per" or lcase(item) = "the" or lcase(item) = "this" or lcase(item) = "to" or lcase(item) = "it" or lcase(item) = "vs." then
        xWord = lcase(item)
    elseif lcase(item) = "ii" or lcase(item) = "iii" or lcase(item) = "iv" or lcase(item) = "vi" or lcase(item) = "vii" or lcase(item) = "viii" or lcase(item) = "ix" then
        xWord = ucase(item)
    end if
    xCompleteWord = xCompleteWord & " " & xWord
next

queryForHeading = xCompleteWord
queryForHeading = Mid(queryForHeading, 2)
queryForHeading = UCase(Mid(queryForHeading, 1, 1)) & Mid(queryForHeading, 2)

I think that you should be using ArrayLists for those conditional statements.

specifically you should store your conjunction words in an ArrayList something like this

Dim conjunctions
Set conjunctions = CreateObject("System.Collections.Arraylist")

conjunctions.Add("a")
conjunctions.Add("an")
conjunctions.Add("and")
conjunctions.Add("as")
conjunctions.Add("at")
conjunctions.Add("by")
' Etc ......

for each item in xTextSplit
    xWord = item
    if conjunctions.contains(lcase(item))
        xWord = lcase(item)
    elseif suffixes.contains(lcase(item))
          xWord = ucase(item)
    end if
    xCompleteWord = xCompleteWord & " " & xWord
next

suffixes would be another ArrayList.  this could be used with the method that Vogel612 suggests.

creating an ArrayList is a better way to perform this task because now you can add more words to the conjunction ArrayList and not have to worry if you found all the instances of it in the code.  It is more Maintainable.

NOTE: I haven't tested this code

 I think that you should be using Dictionary's for those conditional statements.

specifically you should store your conjunction words in a dictionary something like this

Dim conjunctions   ' Create a variable.
Set conjunctions = CreateObject("Scripting.Dictionary")

conjunctions.Add(1,"a")
conjunctions.Add(2,"an")
conjunctions.Add(3,"and")
conjunctions.Add(4, "as")
conjunctions.Add(5, "at")
conjunctions.Add(6, "by")
' Etc ......

for each item in xTextSplit
    xWord = item
    if conjunctions.Exist(lcase(item))
        xWord = lcase(item)
    elseif suffixes.Exist(lcase(item))
          xWord = ucase(item)
    end if
    xCompleteWord = xCompleteWord & " " & xWord
next

suffixes would be another dictionary.  this could be used with the method that Vogel612 suggests.


Golang HTTP requests I'm beginning to learn about Golang and I would like to have some advice about the following program.

package main

import (
    "fmt"
    "net/http"
    "time"
)

const BenchmarkTry = 1000

type PageBenchmark struct {
    url  string
    time int64 // microseconds
}

func execBenchmark(url string, channel chan PageBenchmark) {
    totalExecTimeChan := make(chan int64, BenchmarkTry) // set size to prevent blocked goroutine
    totalExecTime := int64(0)

    // start all the goroutines
    for i := 0; i < BenchmarkTry; i++ {
        go execHttpRequest(url, totalExecTimeChan)
    }

    // catch new values from totalExecTimeChan values come from execHttpRequest()) and add it to the total
    for i := 0; i < BenchmarkTry; i++ {
        totalExecTime += <-totalExecTimeChan // waiting to get a value from one of the goroutines started in the previous for loop
    }

    channel <- PageBenchmark{url, totalExecTime / BenchmarkTry}
}

// exec http request and attach exec time to channel
func execHttpRequest(url string, channel chan int64) {
    begin := time.Now()
    _, _ = http.Get(url)
    channel <- time.Since(begin).Nanoseconds() / 1000000 // convert to milliseconds
}

func main() {
    sites := [...]string{

    }

    pages := [...]string{

    }

    benchmarkChan := make(chan PageBenchmark, len(sites)*len(pages)) // set size to prevent blocked goroutine

    begin := time.Now()
    fmt.Println("Beginning !")

    // start all the goroutines
    for site := range sites {
        for page := range pages {
            go execBenchmark(sites[site]+pages[page], benchmarkChan)
        }
    }

    // catch new values from benchmarkChan and "print" the PageBenchmark
    for i := 0; i < len(sites)*len(pages); i++ {
        benchmark := <-benchmarkChan
        fmt.Printf("Url : %v\nResponse Time : %d ms\n\n", benchmark.url, benchmark.time)
    }

    // print execution time
    fmt.Println("End.")
    fmt.Println(fmt.Sprintf("%d ms", time.Since(begin).Nanoseconds()/1000000))

}

Basically, I'm making HTTP requests (GET method) to multiple URLs on multiple web sites. 1000 requests by URL in this example.

For now, I just want to start some goroutines in this order:

Main: start a benchmark (goroutine) for each web site pages, get the average execution time and print it.
Page routine: start 1000 goroutines (benchmark tries), get the execution times from a channel and store the average execution time in an other channel.
Execute an HTTP request on the page and store the execution time in a channel.

This piece of code works but there may be things I'm missing.

Is the execution scheduling valid?
Is it appropriate to use defined size channels here?
Is there a better/more effective way to achieve this task?

When running your program with the Go race detector, it found no race conditions. That's good!

Given this, I would consider your "execution scheduling" valid.

  Is it appropriate to use defined-size channels here?

Sure. In this case you make the buffer large enough such that it will not be blocked. You can read more about the difference between buffered and unbuffered channels here.

Benchmark through testing

  Is there a better/more effective way to achieve this task?

For benchmarking, it is recommended to use the utilities provided by the testing package.

A lot of this code is boilerplate benchmarking code. With the testing package you can be more confident in the accuracy of your benchmarks, especially since you're using goroutines.

(I will leave switching to the testing package for you.)

Performance bias

sites[site]+pages[page]

Adding strings through the + operator is slow. This could bias your results (ie if you have lots of very long strings), but that also depends on how many sites and pages you test with.

Without knowledge of your full usage, it's hard to tell.

Accuracy

time.Since(begin).Nanoseconds() / 1000000 // convert to milliseconds

I would instead use .Seconds(). Any variation on the scale of milliseconds would be meaningless. From testing with one site and two pages, I received response times of 10288 (10s) and 8128 ms (8s) and an end time of 30073 ms (30s).

Rather than converting to int64 I would keep the type as float64.

String formatting

With the details above:

fmt.Println("End.")
fmt.Println(fmt.Sprintf("%d ms", time.Since(begin).Nanoseconds()/1000000))

Should instead be converted to:

fmt.Printf("End.\nTotal time: %.0fs\n", time.Since(begin).Seconds())

And

fmt.Printf("Url : %v\nResponse Time : %d ms\n\n", benchmark.url, benchmark.time)

Should instead be:

fmt.Printf("Url: %s\nResponse Time: %.0fs\n\n", benchmark.url,
    benchmark.time)

(Notice I use %s rather than %v.)

Variable naming

Variables can have shorter names, especially in shorter functions where their purpose is clear.

totalExecTimeChan becomes timeChan
totalExecTime becomes time
BenchmarkTry becomes tries

I would argue that the names tc and t would be equally fine for the first two.

Capitalization matters in Go. The variable BenchmarkTry and the type PageBenchmark would be exported. In this case it does not make a difference, but for larger programs and packages it would be important.

Miscellaneous

This cast is not needed.

totalExecTime := int64(0)

With the switch to float64, it can instead be:

totalExecTime := 0.0

Some of your comments extend beyond the 80-character column. It is useful to stay within 80 characters when viewing things split across your screen. Instead, move comments to the line before the code. (Some of these comments are superfluous, but you're learning so that's okay.)
Store len(sites)*len(pages) in a constant, rather than recomputing it each time.

Conclusion

Here is the code I ended up with:

package main

import (
    "fmt"
    "net/http"
    "time"
)

const tries = 1000

type pageBenchmark struct {
    url  string
    time float64
}

func execBenchmark(url string, benchmarks chan pageBenchmark) {
    // prevent blocking goroutine
    timeChan := make(chan float64, tries)
    time := 0.0

    // start all requests
    for i := 0; i < tries; i++ {
        go execHTTPRequest(url, timeChan)
    }

    // catch new values from execHTTPRequest()
    for i := 0; i < tries; i++ {
        // wait to get value from goroutine
        time += <-timeChan
    }

    benchmarks <- pageBenchmark{url, time / tries}
}

// exec HTTP request and attach exec time to channel
func execHTTPRequest(url string, timeChan chan float64) {
    begin := time.Now()
    _, _ = http.Get(url)
    timeChan <- time.Since(begin).Seconds()
}

func main() {
    sites := [...]string{
        // sites
    }

    pages := [...]string{
        // pages
    }

    const length = len(sites) * len(pages)

    // set size to prevent blocked goroutine
    benchmarks := make(chan pageBenchmark, length)

    begin := time.Now()

    fmt.Println("Beginning!\n")

    // start all the goroutines
    for site := range sites {
        for page := range pages {
            go execBenchmark(sites[site]+pages[page], benchmarks)
        }
    }

    // catch and print benchmarks
    for i := 0; i < length; i++ {
        b := <-benchmarks
        fmt.Printf("Url: %s\nResponse Time: %.0fs\n\n", b.url, b.time)
    }

    // print total execution time
    fmt.Printf("End.\nTotal time: %.0fs\n", time.Since(begin).Seconds())
}

Hope this helps!


Increase performance of string matching function I've benchmarked my program, and have discovered that the single function taking the most time is the one that does the following.

Takes string that is a delimited list, and splits it into individual strings (Within the program, the individual strings are called statements)
Looks at the individual strings, compares them to a known set of strings (Called a statement library. It contains additional information relating to these strings that I need)

I cannot change the input data, since it comes from several different systems, and the closest thing we can get to something in common is a delimited list of strings.

So, enough background, the first implementation of this was a naive set of LINQ statements:

var statements = textStatements
    .Select(ts => Library.Statements
        .FirstOrDefault(s => ts.Equals(s.FullText, StringComparison.OrdinalIgnoreCase)))
    .Where(s => s != null).ToList();

So, statements is a list of Statement objects, which contain the additional data I need. I figure this is worst case is about O(n^2)-ish.

Once this function was identified as a bottleneck, I made a first attempt at optimizing this function. First, I ensured the split list of statements, and the known list of statements were both sorted, and then implemented this:

var textStatements = SplitStatements(data).ToList();
var statementCount = textStatements.Count;
var libraryCount = Library.Statements.Count;
var libraryOffset = 0;
var foundStatements = new Dictionary<string, Statement>();
for (var i = 0; i < statementCount; i++)
{
    var thisStatement = textStatements[i];
    for (var j = libraryOffset; j < libraryCount; j++)
    {
        var currentLibraryStatement = Library.Statements[j];
        if (string.Equals(thisStatement, currentLibraryStatement.FullText, StringComparison.OrdinalIgnoreCase))
        {
            foundStatements[(currentLibraryStatement.Category.Name + currentLibraryStatement.Code).ToUpperInvariant()] = currentLibraryStatement;
            libraryOffset = j + 1;
            break;
        }
        if (string.Compare(thisStatement, currentLibraryStatement.FullText, StringComparison.OrdinalIgnoreCase) < 0)
        {
            libraryOffset = j;
            break;
        }
    }
}

Essentially, I loop through the statements I need to look up, and start working through the library of statements, remembering where the last statement was found, so I can exclude all statements in the library that are before the last one found.

This did result in a speedup, but not as much as I would hope, hence me throwing this out here to see if I can get another perspective.

You're just looking to find any textStatement's that exist in Library.Statements? A HashSet will make easy work of this:

IEnumerable<string> splitInputStatements = SplitStatements(data);
HashSet<string> inputStatements = new HashSet<string>(splitInputStatements);

// If you're using Library.Statements in this way many times, it might just
// be a good idea to keep all of them cached in a HashSet to begin with so
// you don't have to build this.
IEnumerable<string> libraryStatementTexts = Library.Statements.Select(s => s.FullText);
HashSet<string> libraryStatements = new HashSet<string>(libraryStatementTexts);

// That's it, this is your result:
var matches = inputStatements.Intersect(libraryStatements);

This site has some handy notes for when to use collections of certain types.

Alternatively, you can skip making inputStatements a HashSet and continue using the IEnumerable directly like so::

inputStatements.Where(is => libraryStatements.Contains(is));


Latent Dirichlet Allocation in Python I've recently finished writing a "simple-as-possible" LDA code in Python.

The theory from which I've developed my code can be found in the book Computer Vision by Simon Prince, free (courtesy of Simon Prince) pdf can be found on his website: http://computervisionmodels.com/ - Chapter 20 talks about LDA.
Applied to computer vision, he gives the notation i as the number of images, m as the number of parts or topics, and w as the words.

After re-doing the code today, I've found I get results which I expect (sorting a set of words into two or more topics). I've been comparing to other LDA code which is doing this more accurately and I'm wondering if the way I'm writing the code is making it inefficient. Any feedback appreciated :)

import numpy as np

corpus = open('corpus3.txt').read()

#Creatinig dictionary of unique terms, indexed and counted
dic = {}
arr=[]
arrv=[]
for item in corpus.split():
     if item in dic:
         dic[item] += 1
     else:
         dic[item] = 1

arr = dic.keys()
arrv= dic.values()
arrid=range(0,len(arr))

#Replacing actual words in doc with the word id's
Imgvv=[]
for w in corpus.split():
    for i in arrid:
        if w == arr[i]:
            Imgvv.append(i)

Imgv = [Imgvv] # Array of (array of) words in documents (replaced with id's)
Vocab = arr #Vocab of unique terms

I =  len(Imgv) #Image number
M = 2 # Part number - hardwired (supervised learning)
V = len(Vocab) #vocabulary

#Dirichlet constants
alpha=0.5
beta=0.5

#Initialise the 4 counters used in Gibbs sampling
Na = np.zeros((I, M)) + alpha     # umber of words for each document, topic combo i.e 11, 12,13 -> 21,22,23 array.
Nb = np.zeros(I) + M*alpha        # number of words in each image
Nc = np.zeros((M, V)) + beta      # word count of each topic and vocabulary, times the word is in topic M and is of vocab number 1,2,3, etc..
Nd = np.zeros(M) + V*beta         # number of words in each topic

m_w = [] #topic of the current word
m_i_w=[] # topic of the image of the word
#Filling up counters
for i,img in enumerate(Imgv):
    for w in img:
        m = np.random.randint(0,M)
        m_w.append(m)
        Na[i,m] += 1
        Nb[i] += 1
        Nc[m,w] += 1
        Nd[m] += 1
    m_i_w.append(np.array(m_w)) #creating a relationship between topic to word per doc

#Gibbs Sampling
m_i=[]
q = np.zeros(M)
for t in xrange(500): #Iterations
    for i,img in enumerate(Imgv): #in the Imgv matrix there are i documents which are arrays (img) filled with words
        m_w = m_i_w[i] #Finding topic of word
        Nab = Na[i] #Taking ith row of the Na counter (array)
        for n, w in enumerate(img): #in img there are n words of value w
            m = m_w[n]  # From the intialised/appended topic-word value we draw the "guessed" topic
            Nab[m] -= 1
            Nb[i] -= 1  #In Gibbs Samp. we compute for all values except the current (x,y) position
            Nc[m,w] -= 1 #So we move the counter of this positon down one, compute
            Nd[m] -= 1 #And then add one back after reloading the topic for the word

            q = (Nab*(Nc[:,w]))/((Nb[i])*(Nd)) # computing topic probability
            q_new = np.random.multinomial(1, q/q.sum()).argmax() # choosing new topic based on this
            m_w[n] = q_new      # assigning word to topic, replacing the guessed topic from init.

            Nab[q_new] += 1 #Putting the counters back to original value before redoing process.
            Nb[i] += 1
            Nc[q_new,w] += 1
            Nd[q_new] += 1

WordDist = Nc/Nd[:, np.newaxis]  # This gives us the words per topic

for m in xrange(M): #Displaying results
    for w in np.argsort(-WordDist[m])[:20]:
        print("Topic", m, Vocab[w], WordDist[m,w],arrv[w])

Quickly reading the wikipedia link you provided, it sounds like your implementation slightly differ from the theory, especially the initialization part. I’m not expert, however, and will not try to dig it further. Just going for a style review:

Keep spaces consistent

As it currently stand, your spaces around = or , are not consistent and can be quite uncomfortable to read. Some calculus is also pretty dense and could gain some readability by using spaces.

Use functions

You could more easily test your script and figure why you don't get the results you're expecting if you split it in small functions. Reading files, indexing words, initializing computation and performing LDA seems to be the 4 tasks you do out of pretty-printing the results.

Be nice to the memory

Twice in your script, you use more than three times the space needed to store 'corpus.txt': corpus, dic and corpus.split() all contains each word of 'corpus.txt' with additional data. I don't know how big is the file but this is only one file, LDA allows for more (namely I to stay in your code context).

Since you're already reading through the content of the file twice, why not open the files twice and process them line by line each time to avoid overflooding the memory?

And talking about handling more files, your code should allow that more easily. Using functions with variable number of arguments is a way of doing it.

Constants

It is best to define them at the top of the file with an ALL_CAPS name. alpha and beta can qualify (they can be seen as variable since they are parameters of LDA), but more importantly the number of iteration is one of them.

Building data structures

To count elements in an iterable, you can use the collections.Counter class which is a subclass of dict:

words = Counter(data.split())

is more readable and understandable than

words = {}
for w in data.split():
    try:
        words[w] = words[w] + 1
    except KeyError:
        words[w] = 1

As such, it is often recommended to use list-comprehension rather than:

data = []
for elem in other_data:
    data.append(process(elem))

Incomplete improvement

(Based on Rev 2 of the question)

import numpy as np
from collections import Counter

ALPHA = 100
BETA = 5
ITERATIONS = 1000

def read_corpuses(*filenames):
    words = Counter()
    for corpus_file in filenames:
        with open(corpus_file) as corpus:
            words.update(word for line in corpus for word in line.split())
    return words

def compute_image(vocabulary, corpus_filename):
    with open(corpus_filename) as corpus:
        return [vocabulary.index(word) for line in corpus for word in line.split()]

def init_LDA(images, M, V):
    I = len(images)
    Na = np.zeros((I, M)) + ALPHA     # umber of words for each document, topic combo i.e 11, 12,13 -> 21,22,23 array.
    Nb = np.zeros(I) + M*ALPHA        # number of words in each image
    Nc = np.zeros((M, V)) + BETA      # word count of each topic and vocabulary, times the word is in topic M and is of vocab number 1,2,3, etc..
    Nd = np.zeros(M) + V*BETA         # number of words in each topic

    def inner(i, w):
        m = np.random.randint(0, M)
        Na[i, m] += 1
        Nb[i] += 1
        Nc[m, w-1] += 1
        Nd[m] += 1
        return m

    return Na, Nb, Nc, Nd, [[inner(i, w) for w in image] for i, image in enumerate(images)]

def LDA(topics, *filenames):
    words = read_corpuses(*filenames)
    vocabulary = words.keys()

    images = [compute_image(vocabulary, corpus) for corpus in filenames]

    Na, Nb, Nc, Nd, topic_of_words_per_image = init_LDA(images, topics, len(vocabulary))

    #Gibbs Sampling
    probabilities = np.zeros(topics)
    for _ in xrange(ITERATIONS):

        for i, image in enumerate(images):
            topic_per_word = topic_of_words_per_image[i]
            for n, w in enumerate(image):
                m = topic_per_word[n]

                Na[i, m] -= 1
                Nb[i] -= 1
                Nc[m, w-1] -= 1
                Nd[m] -= 1

                # computing topic probability
                probabilities[m] = Na[i, m] * Nc[m, w-1]/(Nb[i] * Nd[m])
                # choosing new topic based on this
                q = np.random.multinomial(1, probabilities/probabilities.sum()).argmax()
                # assigning word to topic
                topic_per_word[n] = q

                Na[i, q] += 1
                Nb[i] += 1
                Nc[q, w-1] += 1
                Nd[q] += 1

    distances = Nc/Nd[:, np.newaxis] #Words by Topic and printing
    return distances, vocabulary, words

if __name__ == '__main__':
    topics = 2
    #Add as many filenames as needed, like LDA(topics, 'corpus1.txt', 'corpus2.txt', 'corpus3.txt')
    distances, vocabulary, words_count = LDA(topics, 'corpus.txt')

    for topic in xrange(topics):
        for word_index in np.argsort(-distances[topic])[:20]:
            word = vocabulary[word_index]
            print "Topic", topic, word, distances[topic, word_index], words_count[word]

Things left to improve

You corpuses might contain words with punctuation and capitalization. You might want to split things according to string.punctuation and lowercase each word to avoid creating several keys for a single word. You may want to filter on the length of the string in doing so, or del words[''] afterward, depending on how you do things.
Naming is not optimal and hard to follow. Better take names of the variables from the LDA theory, like theta, phi instead of Na, Nc. Same goes for loop variables, some are not intuitive to be able to follow your implementation by looking at the theory from your wikipedia link.
As said at the beginning of the post, init_LDA might not compute the correct arrays.


Haskell Pig Latin Translator - v2 Thanks to Gurkenglas for the help with the previous iteration: Haskell - Pig Latin Translator!

Given the constraint that the newtypes are required, what improvements could be made to the following Pig Latin translator?

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE InstanceSigs #-}

import Control.Monad (when)
import Data.Char (toLower, toUpper)
import System.IO (hFlush, stdout)

newtype PigLatin = PigLatin String

instance Show PigLatin where
  show :: PigLatin -> String
  show (PigLatin x) = x

instance Monoid PigLatin where
  mempty :: PigLatin
  mempty = PigLatin ""

  mappend :: PigLatin -> PigLatin -> PigLatin
  mappend (PigLatin a) (PigLatin b) = PigLatin $ a ++ " " ++ b

plMap :: (String -> String) -> PigLatin -> PigLatin
plMap f (PigLatin x) = PigLatin $ f x

newtype English = English String
  deriving (Eq)

safeTail :: [a] -> [a]
safeTail (_:xs) = xs
safeTail [] = []

quitCommand :: English
quitCommand = English "\\q"

wordToPig :: English -> PigLatin
wordToPig (English word@(x:_)) = PigLatin $ if isVowel x
                                              then word ++ "yay"
                                              else rearrangedWord ++ "ay"
    where rearrangedWord = drop (length initialConsonants) word ++ initialConsonants
          initialConsonants = takeWhile isConsonant word
          isConsonant = not . isVowel
wordToPig (English "") = PigLatin ""

isVowel :: Char -> Bool
isVowel letter = letter `elem` ['a', 'e', 'i', 'o', 'u']

englishWords :: English -> [English]
englishWords (English input) = map English $ words input

sentenceToPig :: English -> PigLatin
sentenceToPig = plMap (capitalize . safeTail) . foldl mappend mempty . map wordToPig . englishWords

capitalize :: String -> String
capitalize (x:xs) = toUpper x : map toLower xs
capitalize [] = ""

putStrNow :: String -> IO ()
putStrNow message = do
  putStr message
  hFlush stdout

prompt :: String -> IO English
prompt promptInput = do
  putStrNow promptInput
  input <- getLine
  return $ English input

main :: IO ()
main = do
    input <- prompt "> "
    when (input /= quitCommand) $ do
      print $ sentenceToPig input
      main

Problem 1: Monoid

One subtle problem here:

instance Monoid PigLatin where
  mempty :: PigLatin
  mempty = PigLatin ""

  mappend :: PigLatin -> PigLatin -> PigLatin
  mappend (PigLatin a) (PigLatin b) = PigLatin $ a ++ " " ++ b

While it may not seem it, this is in fact an invalid Monoid instance. When we write Monoid instances we want certain laws to hold true so we can reason about them more easily. One such law: mappend mempty x = x = mappend x mempty. We want mempty to act as an "identity element" (like adding zero to or multiplying one by an integer). The extra space character makes this impossible. If the Monoid instance had been lawful, we could have replaced foldl mappend mempty with mconcat.

So the first thing I would do is to excise this Monoid instance and instead use unwords, as we'll detail below. This approach has the advantage of letting us delete safeTail.

Problem 2: Slicing and dicing newtypes

The other thing we want to tackle is the problem of lifting String operations into our newtypes. We really want to lift unwords :: [String] -> String to unwords :: [PigLatin] -> [PigLatin]; that would obviate the need for the fold and the Monoid instance altogether. We also want to lift String -> String to PigLatin -> PigLatin, as evidenced by our plMap function. There's a similar problem with englishWords: we have a function String -> [String] but we want English -> [English] Haskell programmers are extraordinarily lazy and so we ask ourselves, how can we do this in the least amount of code possible?.

A common trick is to add a type variable:

newtype PigLatin a = PigLatin a
  deriving (Functor)

newtype English a = English a
  deriving (Eq, Functor, Foldable, Traversable)

This lets us derive instances for Functor, Foldable, and Traversable. It even admits an Applicative instance:

instance Applicative PigLatin where
  pure =
    PigLatin
  (<*>) (PigLatin a2b) (PigLatin a) =
    PigLatin (a2b a)

But why? Let's break down these typeclasses one by one.

Functor

One of our best friends. With Functor, plMap = fmap. The compiler automatically knows how to lift functions of type String -> String to PigLatin String -> PigLatin String. Not having to write any code is the best code there is. In fact, the compiler can even lift any type a -> a to PigLatin a -> PigLatin a even if in the end we only want to deal with PigLatin String values.

Foldable and Traversable

Having these two instances around permits the almight traverse. This humbly named function does something very very useful as it has type (a -> [b]) -> English a -> [English b], which is exactly what we need to lift words up through our English newtype. When we choose to equip English with a Foldable and a Traversable instance we are granted the keys to this wonderful kingdom. The end result is this function

englishWords :: English String -> [English String]
englishWords =
  traverse words

Which is hardly long enough to worth defining!

Applicative

I fibbed earlier as it turns out that traverse actually has type

(Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

This unwieldy amalgam of variables and arrows can be broken down thusly. You can choose any types f, t and as long as there's an Applicative f and a Traversable t instance the compiler will do what you please.

Up above we chose f ~ [] (the list type) and t ~ English. What if instead we were to choose f ~ PigLatin and t ~ []? Well then we would have a very interesting function of type (a -> PigLatin b) -> [a] -> PigLatin [b].

Notice that wordToPig has type English String -> PigLatin String, which means traverse wordToPig would have type [English String] -> PigLatin [String], which is exactly what we want. Why?

sentenceToPig :: English String -> PigLatin String
sentenceToPig =
  fmap (capitalize . unwords) . traverse wordToPig . traverse words

Because that allows us to reach for our old friend fmap. capitalize . unwords takes [String] to String, which means when we lift it up with fmap we get a function PigLatin [String] -> PigLatin String. Exactly what we need.

Coercible, the hidden typeclass

One thing you may not be aware of is that GHC generates a Coercible instance for all newtypes. What this means is a little too complicated to go into detail here, but the end result is that you can type coerce (PigLatin "hello") :: String and get back "hello" :: String. Both the "hello" :: String and the PigLatin "hello" :: PigLatin String have the same in-memory representation, as guaranteed by the newtype keyword, and thus this poses no problem for the runtime. I like to use it for short scripts and it's especially handing for printing out newtypes. I noticed you defined a Show instance, and I think that's OK too. But I thought I'd bring it up since it's often overlooked.

Altogether now

{-# LANGUAGE DeriveFunctor     #-}
{-# LANGUAGE DeriveTraversable #-}

import Control.Monad (when)
import Data.Coerce (coerce)
import Data.Char (toLower, toUpper)
import System.IO (hFlush, stdout)

newtype PigLatin a = PigLatin a
  deriving (Functor)

newtype English a = English a
  deriving (Eq, Functor, Foldable, Traversable)

instance Applicative PigLatin where
  pure = PigLatin
  (<*>) (PigLatin a2b) (PigLatin a) = PigLatin (a2b a)

quitCommand :: English String
quitCommand = English "\\q"

wordToPig :: English String -> PigLatin String
wordToPig (English word@(x:_)) =
  PigLatin $ if isVowel x
             then word ++ "yay"
             else rearrangedWord ++ "ay"
  where
    rearrangedWord =
      drop (length initialConsonants) word ++ initialConsonants
    initialConsonants =
      takeWhile isConsonant word
    isConsonant =
      not . isVowel
wordToPig (English "") =
  PigLatin ""

isVowel :: Char -> Bool
isVowel letter = letter `elem` "aeiou"

sentenceToPig :: English String -> PigLatin String
sentenceToPig =
  fmap (capitalize . unwords) . traverse wordToPig . traverse words

capitalize :: String -> String
capitalize (x:xs) = toUpper x : map toLower xs
capitalize [] = ""

putStrNow :: String -> IO ()
putStrNow message = do
  putStr message
  hFlush stdout

prompt :: String -> IO (English String)
prompt promptInput = do
  putStrNow promptInput
  input <- getLine
  return $ English input

main :: IO ()
main = do
  input <- prompt "> "
  when (input /= quitCommand) $ do
    putStrLn . coerce $ sentenceToPig input
    main


Creating a function with limited number of args in python I am learning programming, and I am thinking how to improve this code in a more pythonic way.

I have a function with number of arguments. However, any caller of the function can specify the arguments, and depending on the arguments given, I will return the dictionary. The given arguments must be only from the listed arguments.

The code that I have below has so much duplication (I remove carPower, carTime and carLease however it will do the same if/else part)
How can I improve this?

def creating_result(my_struct,
                carColour=None,
                carPrice=None,
                carGas=None,
                carBrand=None,
                carSpeed=None,
                carOwner=None,
                carPower=None,
                carTime=None,
                carLease=None,
                carEngine=None,
                carType=None
                ):

     if carColour and isinstance(carColour, list):
        my_struct["carColour"] = { "thekey" : carColour}
     elif carColour:
        my_struct["carColour"] = carColour

     if carPrice and isinstance(carPrice, list):
        my_struct["carPrice"] = { "thekey" : carPrice}
     elif carPrice:
        my_struct["carPrice"] = carPrice

     if carGas and isinstance(carGas, list):
        my_struct["carGas"] = { "thekey" : carGas}
     elif carGas:
        my_struct["carGas"] = carGas

     if carBrand and isinstance(carBrand, list):
        my_struct["carBrand"] = { "thekey" : carBrand}
     elif carBrand:
        my_struct["carBrand"] = carBrand

     if carSpeed and isinstance(carSpeed, list):
        my_struct["carSpeed"] = { "thekey" : carSpeed}
     elif carSpeed:
        my_struct["carSpeed"] = carSpeed

     if carEngine:
        my_struct["carEngine"] = carEngine

     if carPrice:
        my_struct["carPrice"] = carPrice

     if carType:
        my_struct["carType"] = carType

     print "my_struct is ", my_struct

if __name__ == "__main__":
    # test 1st caller
    my_dict = {}
    creating_result(my_dict, carPrice=1, carColour="red")

    # test 2nd caller
    my_dict = {}
    creating_result(my_dict, carSpeed="200", carType="SUV", carPrice=300)

In case I can not change the list of arguments of the function above, how can I improve the (if/else) of the function above?

In all programming language, it is better that a function's name is a verb, or start with a verb. In your case, I would use create_result() instead of creating_result().

One this transformation is done, you would think of a better name for this function as it is quite too generic in its meaning. create_car() would be better and more meaningful in your context.

For the parameters you are passing, they should be written following the snake_name convention. Meaning, for example, carColour becomes car_color, carPrice becomes car_price, ... and so on.

More important: Regardless of the purpose of the parameters you are passing to the creating_result() function, their number is quite much which thing should lead to creating a class and use them as instance attributes.


Use of Exception to log execution stack trace I've been back and forth with a colleague over the use of Throwable.fillInStackTrace. This Log class is meant to wrap the Simple Logging Facade for Java.

public class Log {
    private static final org.slf4j.Logger log = org.slf4j.LoggerFactory.getLogger(Log.class);

    private String stackTrace(Exception cause) {
        if (cause == null)
            return "";
        StringWriter sw = new StringWriter(1024);
        final PrintWriter pw = new PrintWriter(sw);
        cause.printStackTrace(pw);
        pw.flush();
        return sw.toString();
    }

    public void warn(Exception cause, String message) {
        String output = message + "\n" + stackTrace(cause);
        log.warn(output);
    }

    // debug(...), info(...), etc.
}

But it is being used thusly:

new Log()
    .warn((Exception)new RuntimeException().fillInStackTrace(), "I'm warning you.");

When reviewing this, my comments included things like the "Exceptions are exceptional" idiom.

But when I mentioned that creating a stack trace is an expensive operation and should be avoided, I was told that this used to be true in the past [e.g. with JVM implementations] but is now longer true [i.e. This has been fixed/optimized].

I was not aware of this development, so I checked around and most of the SO questions seem to indicate that making a stack trace is expensive.

Does this code seem reasonable? Would you consider this bad practice?

It seems like you're working harder than you need to. Instead of this:

public void warn(Exception cause, String message) {
    String output = message + "\n" + stackTrace(cause);
    log.warn(output);
}

I think you could do this, and no need for the stackTrace method:

public void warn(Exception cause, String message) {
    log.error(cause.getMessage() + " " + message, cause);
}

Moreover, notice how common libraries use a String as the first parameter of logging methods, and a Throwable as the second. I suggest to follow that example and reorder your parameters.


VBScript for AD account creation Does the following code look okay? Want to see if anyone can spot any mistakes I may have made. This will be pulling from a pre-formatted Excel document - I have already specified all needed Cell locations.

Things I want clarified:

How many times can you invoke SetInfo and did I use it more than needed? I was under the impression that a SetInfo would be needed before a SetPassword can be used, but I could be very wrong.
Does this line look okay? Was I correct to separate multiple cells using a comma in order to put all the info together? I know it worked with an Echo command:

Set objUser = objOU.Create _
("User", "cn=" & objExcel.Cells(intRow, 3).Value, objExcel.Cells(intRow, 2).Value, objExcel.Cells(intRow, 19).Value)

Is this the correct code for setting a password to never expire?

objUser.Put "userAccountControl", intUAC XOR _
ADS_UF_DONT_EXPIRE_PASSWD

Full code below, I'd appreciate any feedback on anything else that is found.

Set objExcel = CreateObject("Excel.Application")
Set objWorkbook = objExcel.Workbooks.Open _
    ("C:\Book1.xls")
intRow = 2
Do Until objExcel.Cells(intRow,1).Value = ""
    Set objOU = GetObject _
    ("ou=" & objExcel.Cells(intRow, 13).Value & _
        ", dc=satdc, dc=com")
    Set objUser = objOU.Create _
        ("User", "cn=" & objExcel.Cells(intRow, 3).Value, objExcel.Cells(intRow, 2).Value, objExcel.Cells(intRow, 19).Value)
    objUser.sAMAccountName = objExcel.Cells(intRow, 19).Value & ".sat"
    objUser.GivenName = objExcel.Cells(intRow, 3).Value
    objUser.SN = objExcel.Cells(intRow, 2).Value
    objUser.SetInfo
    objUser.AccountDisabled = False
    objUser.AccountExpirationDate = Date + 365
    objUser.SetPassword objExcel.Cells(intRow, 9).Value
    objUser.SetInfo
    objUser.Put "userAccountControl", intUAC XOR _
        ADS_UF_DONT_EXPIRE_PASSWD
    objUser.HomeDirectory = "\\satdc" & "\" & "Users" & "\" & _
        objUser.Get("sAMAccountName")
    objUser.homeDrive = "U:"
    objUser.SetInfo
    intRow = intRow + 1
Loop
objExcel.Quit

Naming: Hungarian Notation is the DEVIL.
It makes the reader want to see your code burn in eternal flames.

https://simpsonswiki.com/wiki/Flanders_the_Devil

objExcel would be better off as xlApp or excelApp
objUser is dying to call itself something like adUser
intRow wants to be called xlRow or just row
intUAC is silently begging for a more descriptive name
objOU wants to shoot whoever named it that

Now, whether your code is correct or not is off-topic for this site; since this question hasn't been closed as off-topic yet, I'm going to assume you've got working code.
Do Until objExcel.Cells(intRow,1).Value = ""

I'd use vbNullString here instead of "". It makes the intent clearer, and the non-string takes up 0 bytes. "" eats 6 bytes for no reason - StrPtr(vbNullString) is 0; StrPtr("") is a non-zero memory address.
The repeated assignments on objUser are a missed opportunity of using a With block:
With objOU.Create("User", "cn=" & objExcel.Cells(intRow, 3).Value, _
                          objExcel.Cells(intRow, 2).Value, _
                          objExcel.Cells(intRow, 19).Value)

    .SAMAccountName = objExcel.Cells(intRow, 19).Value & ".sat"
    .GivenName = objExcel.Cells(intRow, 3).Value
    .SN = objExcel.Cells(intRow, 2).Value
    .AccountDisabled = False
    .AccountExpirationDate = Date + 365
    '...

End With

Your usage of line continuation characters is... well, you use it in weird places. Actually, everywhere you've used it, I wouldn't have. Notice in the above snippet, how I used it to line up the parameters.