Thread-safe linked list review I want to implement a thread-safe singly linked list in C. Its nodes contain unique entries and I only need functions to add nodes (to head only), remove nodes and to locate a specific node.

I am reasonably confident of the linked-list logic (any performance tips would be greatly appreciated though), but I am more concerned with my thread-safety logic. This is my first real foray into coding a thread-safe data structure. Is it optimal? Is it overkill? Is there a more performant way to get thread-safety for this data structure?

Thread-safety definitions from header:

#define MY_SPINLOCK_INIT 0
typedef volatile int MYSpinLock;

__attribute__((always_inline))
static inline void MYSpinLockLock(MYSpinLock *lock) {
    while (__sync_lock_test_and_set(lock, 1))
        while (*lock)
            ;
}
__attribute__((always_inline))
static inline void MYSpinLockUnlock(MYSpinLock *lock) {
    __sync_lock_release(lock);
}

Struct definitions:

typedef struct {
    const void *_key;
    uintptr_t _value;
} MYEntry;

typedef struct __MYNode {
    MYEntry _entry;
    struct __MYNode *_next;
} MYNode;

typedef struct {
    MYNode *_head;
    MYSpinLock _lockLL;
} MYLinkedList;

Implementation:

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &(list->_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)

MYLinkedList *MYLinkedListConstruct() {
    MYLinkedList *list = malloc(sizeof(MYLinkedList));
    list->_head = NULL;
    list->_lockLL = MY_SPINLOCK_INIT;
    return list;
}

void MYLinkedListFree(MYLinkedList *list) {
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    MYNode *next;
    while (node != NULL) {
        next = node->_next;
        free(node);
        node = next;
    }

    MY_LISTLOCK_UNLOCK;
    free(list);
}

void MYLinkedListAdd(MYLinkedList *list, MYEntry *entry) {
    MY_LISTLOCK_LOCK;

    MYNode *oldHead = list->_head;
    MYNode *newHead = malloc(sizeof(MYNode));
    newHead->_entry = *entry;
    newHead->_next = oldHead;
    list->_head = newHead;

    MY_LISTLOCK_UNLOCK;
}

MYBool MYLinkedListRemoveNodeWithEntryKey(MYLinkedList *list, void *keyOfNodeToRemove) {

    if (keyOfNodeToRemove == NULL) return MYFalse;
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    MYNode *prev = NULL;
    while (node != NULL) {
        // We found it, break
        if (node->_entry._key == keyOfNodeToRemove) break;

        prev = node;
        node = node->_next;
    }

    // We never found it
    if (node == NULL) {
        MY_LISTLOCK_UNLOCK;
        return MYFalse;
    }

    // We found it
    if (prev == NULL) {
        list->_head = node->_next;
        free(node);
    }
    else {
        prev->_next = node->_next;
        free(node);
    }

    MY_LISTLOCK_UNLOCK;
    return MYTrue;
}

MYNode *MYLinkedListFindNodeWithKey(MYLinkedList *list, void *keyToFind) {

    if (keyToFind == NULL) return NULL;
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    while (node != NULL) {
        if (node->_entry._key == keyToFind) {
            MY_LISTLOCK_UNLOCK;
            return node;
        }
        node = node->_next;
    }

    MY_LISTLOCK_UNLOCK;
    return NULL;
}

Is there a more performant way to get thread-safety for this data structure?

It all depends on how the list will be used. Just a few examples:

Reads are more common than writes - use separate read/write locks.
Average list is short - use copy-on-write array instead of linked list.
Average list is long - use more efficient search method.
Lots of threads access list - use mutex instead of spinlock to avoid wasted cycles.
Lots of elements is added/removed in bulk - use external lock.

Have you actually measured performance in real world scenarios and identified bottlenecks? It looks like most of it is prematurely optimized.

__attribute__((always_inline))

Is this really necessary? Does it bring any measurable performance gain?

while (__sync_lock_test_and_set(lock, 1))
    while (*lock)

I do not understand this second while loop. Why are you checking the value twice?

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &(list->_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)

Avoid macros which can be replaced with functions.

MYBool

Use bool from stdbool.h.


Finding the largest averaged array Sometimes the best way to teach is show what you feel is a shiny approach instead of letting a student muddle through coding and potentially loose a future brilliant coder.

This is what I would show for 'Determine the largest averaged array`. Please review any and all aspects.

'use strict';
//Return the average of 1 array
function arrayAverage(array) {
  var length = array.length,
      sum = 0,
      i;
  for (i = 0; i < length; i++) {
    sum += array[i];
  }
  return sum / length;
}

//Compare 2 arrays, return the array with the largest average
//If the averages are equal, return array2
function largestAveragedArray(array1, array2) {

  return arrayAverage(array1) > arrayAverage(array2) ? array1 : array2;
}

//Figure out which array is largest, return `first` or `second` accordingly
function compare(array1, array2) {
  var largest = largestAveragedArray(array1, array2);
  return largest == array1 ? 'first' : 'second';
}

var smaller = [100, 80],
    larger = [100, 100];

document.write(compare(larger, smaller) + '<br>' + compare(smaller, larger));

First of all, a minor complaint, but be careful when using 'use strict'; at a file level—when concatenating JavaScript files for minification, this can have adverse affects. Whenever possible, use it at the top of a function instead.

Anyway, on to the actual code. Your arrayAverage function is fine, but it could be improved and made more explicit by using a more functional style. The .reduce function is perfect for this case, turning the function into a simple one-liner:

function arrayAverage(array) {
  return array.reduce(function (a, b) { return a + b; }) / array.length;
}

Your compare function is, frankly, rather odd. I see three main problems with it:

It does not handle arrays that have equal averages very well. Simply preferring the second array is not a good compromise.
Returning strings for the result is a little strange and unnatural. While there are no enums in a language like JavaScript, using string literals is not a good replacement.
The name compare is very generic and doesn't explain what the function does at all.

To fix all these problems, I propose the following function:

function arrayCompare(arrayA, arrayB) {
  var averageA = arrayAverage(arrayA),
      averageB = arrayAverage(arrayB);
  return averageA < averageB ? -1
       : averageA > averageB ?  1
                             :  0;
}

This is clearer, and it handles the equality case more elegantly. If you really hate nested conditional expressions with a passion, you could use a set of if statements instead, but I think this is perfectly readable when properly formatted.

This change eliminates the need for the largestAveragedArray function entirely, simplifying the code somewhat. As a final note, document.write makes me cringe, but I understand that it's useful in code snippets, so I'll let it slide here. Just don't use it in a real project.

(function () {
  'use strict';

  // returns the average of a single array
  function arrayAverage(array) {
    return array.reduce(function (a, b) { return a + b; }) / array.length;
  }

  // compares two arrays;
  // returns -1 if avg(a) < avg(b), 1 if avg(a) > avg(b), or 0 if avg(a) = avg(b)
  function arrayCompare(arrayA, arrayB) {
    var averageA = arrayAverage(arrayA),
        averageB = arrayAverage(arrayB);
    return averageA < averageB ? -1
         : averageA > averageB ?  1
                               :  0;
  }

  var smaller = [100, 80],
      larger = [100, 100];

  document.write(arrayCompare(smaller, larger) + '
' + arrayCompare(larger, smaller) + '
' + arrayCompare(smaller, smaller));
})();


Saving the contents of a TextArea to a file Can this method be modified to be more efficient?

public void saveFile(File file, TextArea textArea) {
    if (file != null) {
        String filePath = file.getAbsolutePath();
        try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(filePath))) {
            writer.write(textArea.getText());
        } catch (IOException e) {
            System.out.println("savefile exception");
        }
    }
}

Some suggestion:

A "save to file" method without a valid file is useless. If the file is null your method is a no-op without a warning for the user.
Code reuse: your code works with TextArea only. A better solution would be a String argument instead of TextArea.
Method name: "saveFile" is too generic
Exception handling: you should catch the exception only if you know how to handle it or if you enrich the exception with new information before rethrow it

My version:

public void writeStringToFile(File file, String text) throws IOException {
    if (file == null)
        throw new IllegalArgumentException("file cannot be null");

    if (text == null)
        throw new IllegalArgumentException("text cannot be null");

    String filePath = file.getAbsolutePath();

    try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(filePath))) {
        writer.write(text);
    }
}

But... DON'T REINVENT THE WHEEL!

A better solution is the Apache FileUtils class, see writeStringToFile method.

ps: English is not my mother tongue


Python Secure Implementation Of AES-256-CTR Using Cryptography.Hazmat I've implemented a wrapper for AES 256 CTR mode using the cryptography.hazmat module, I am wondering if there are any vulnerabilities in my implementation, specifically about the counter and its encoding. Here is the code:

from cryptography.hazmat.primitives.ciphers import Cipher
from cryptography.hazmat.primitives.ciphers.algorithms import AES
from cryptography.hazmat.primitives.ciphers.modes import CTR
from cryptography.hazmat.backends import default_backend as backend
from base58 import b58encode,b58decode
import os

#AES Cipher Class
class AES_Cipher:
  #Initialise Class, Set Countner And Key
  def __init__(self,key):
    self.counter = 0
    self.key = key

    #AES 256 Requirement
    assert len(self.key) == 32

  #Encryption Function
  def encrypt(self,plain_text):
    plain_text = plain_text.encode()
    self.counter += 1
    cipher = Cipher(AES(self.key),CTR(self.padCounter()),backend())
    encryption_engine = cipher.encryptor()
    cipher_text = self.padCounter() + encryption_engine.update(plain_text) + encryption_engine.finalize()
    return b58encode(cipher_text)

  #Decryption Function
  def decrypt(self,cipher_text):
    cipher_text = b58decode(cipher_text)
    self.counter = cipher_text[:16]
    cipher = Cipher(AES(self.key),CTR(self.counter),backend())
    decryption_engine = cipher.decryptor()
    plain_text = decryption_engine.update(cipher_text[16:]) + decryption_engine.finalize()
    return plain_text.decode()

  #Pad The Counter Into 16 Bytes
  def padCounter(self):
    return bytes(str(self.counter).zfill(16),"ascii")

Usage:

    key = os.urandom(32)
    aes_engine = AES_Cipher(key)
    aes_engine.encrypt("hello world")
    aes_engine.decrypt(b"7WkHvZEJRr8yMEasvh3TESoW8nBTkEUNVu2Li")

A warning

You probably already saw this coming, but: I would be remiss if I didn't say it. 'Rolling your own to learn' is fine, but perhaps the most difficult and dangerous place to do it is cryptography. Cryptographic security is notoriously difficult to ascertain. The less you do yourself and the more you leave to well-reviewed, well-established libraries, the better.

Indentation

Python code typically sees three- or four-space tabs by convention; two is a little low.

Type hints

PEP484 allows for this:

def __init__(self,key):

to be (at a guess)

def __init__(self, key: bytes):

and this:

def encrypt(self,plain_text):

to become

def encrypt(self,plain_text: str) -> str:

Helpful comments

This isn't one:

#Encryption Function

you're better off either deleting it, or writing a docstring with non-obvious documentation:

def encrypt(self,plain_text):
    """
    Encrypts a string using this object's key and the AES algorithm.
    Returns the encrypted result, as a base58-encoded string.
    """


Finding customer searches and graphing their items One of the reports I am working on requires me to locate searches a customer makes, and graph them in certain manners.

I have one query I'm particularly concerned about. This one takes the most amount of time (relative to the batch) and seems quite ugly to me.

Essentially, this should graph the search results by the day of the week and give me: the total number of searches, the average searches per week day, the number of searches that had no returned results, and the percent of searches that have no results.

SELECT
    DATENAME(WEEKDAY, [AtDateTime]) AS [Day of Week]
    ,COUNT(*) AS [Number of Searches]
    ,CAST(CAST(COUNT(*) AS DECIMAL(10, 2)) / COUNT(DISTINCT CONVERT(DATE, [AtDateTime])) AS DECIMAL(10, 2)) AS [Average Searches per Day]
    ,SUM(CASE WHEN [NumFound] = 0 THEN 1 ELSE 0 END) AS [Number of Searches with no Results]
    ,CAST(CAST(SUM(CASE WHEN [NumFound] = 0 THEN 1 ELSE 0 END) AS DECIMAL(10, 2)) / COUNT(*) AS DECIMAL(10, 4)) AS [Percent of Searches with no Results]
FROM [DB].[dbo].[SearchHistory]
WHERE NOT EXISTS
(
    SELECT 1 FROM [DB].[dbo].[CustomerExclusions]
    WHERE [CustomerNumber] = [SearchHistory].[CustomerNumber]
    AND [ExcludeFromSearch] = 1
)
GROUP BY DATENAME(WEEKDAY, [AtDateTime]), DATEPART(WEEKDAY, [AtDateTime])
ORDER BY DATEPART(WEEKDAY, [AtDateTime])

Any advice/critique is welcome.

DDL for the SearchHistory table:

CREATE TABLE [dbo].[SearchHistory](
    [CustomerNumber] [char](8) NOT NULL,
    [Username] [varchar](16) NOT NULL,
    [AtDateTime] [datetime2](7) NOT NULL,
    [Terms] [varchar](128) NOT NULL,
    [NumFound] [int] NOT NULL,
    [NumInStock] [int] NOT NULL
) ON [PRIMARY]
ALTER TABLE [dbo].[SearchHistory] ADD  CONSTRAINT [DF_SearchHistory_AtDateTime]  DEFAULT (sysdatetime()) FOR [AtDateTime]
GO

DDL for the CustomerExclusions table:

CREATE TABLE [dbo].[CustomerExclusions](
    [CustomerNumber] [char](8) NOT NULL,
    [ExcludeFromSearch] [bit] NOT NULL,
    [ExcludeFromErrors] [bit] NOT NULL,
    [ExcludeFromPageHits] [bit] NOT NULL,
 CONSTRAINT [PK_CustomerExclusions] PRIMARY KEY CLUSTERED
(
    [CustomerNumber] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

The indexes on SearchHistory are as follows:

CREATE NONCLUSTERED INDEX [IX_SearchHistory_CustomerNumber_Username_AtDateTime_Terms] ON [dbo].[SearchHistory]
(
    [CustomerNumber] ASC,
    [Username] ASC,
    [AtDateTime] ASC,
    [Terms] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO
CREATE NONCLUSTERED INDEX [IX_SearchHistory_NumFound] ON [dbo].[SearchHistory]
(
    [NumFound] ASC
)
INCLUDE (   [CustomerNumber],
    [Terms]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO
CREATE NONCLUSTERED INDEX [IX_SearchHistory_NumFound_CustomerNumber] ON [dbo].[SearchHistory]
(
    [NumFound] ASC,
    [CustomerNumber] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

The CustomerExclusions table has no indexes on it, apart from the PK.

This is for SQL Server 2012.

There are two records in CustomerExclusions, and almost 22k records in SearchHistory. When both filters are applied, both records in CustomerExclusions match ExcludeFromSearch = 1, and ~17k records in SearchHistory are returned when the CustomerExclusions filter is applied.

Regarding performance the code looks fine. Possibly you are missing useful indexes.

As far as the code itself is concerned I have the following observations.

Remove three part names.

[DB].[dbo].[SearchHistory] and [DB].[dbo].[CustomerExclusions]

It is common to want to run queries against different versions of the database. Hardcoding the database name in to SQL makes this harder.

If this SQL lives inside a stored proc in a copy of the database DB_copy on the same instance as DB you may be unaware that this is, in fact, referencing a different database for some time. Similarly if the SQL is sent by an application it is likely that most people will assume that changing the "Initial Catalogue" in the connection string will change the tables being queried.

Add table aliases and use them for all columns in the correlated sub query

/*Original Code*/
FROM [DB].[dbo].[SearchHistory]
WHERE NOT EXISTS
(
    SELECT 1 FROM [DB].[dbo].[CustomerExclusions]
    WHERE [CustomerNumber] = [SearchHistory].[CustomerNumber]
    AND [ExcludeFromSearch] = 1
)

/*Rewritten Code*/
FROM   dbo.SearchHistory sh
WHERE  NOT EXISTS (SELECT *
                   FROM   dbo.CustomerExclusions ce
                   WHERE  ce.CustomerNumber = sh.CustomerNumber
                          AND ce.ExcludeFromSearch = 1)

If the table CustomerExclusions does not have any columns called CustomerNumber or ExcludeFromSearch but these do exist in SearchHistory then the original correlated sub query will resolve them from the outer scope giving you incorrect results rather than an error message. Using two part names as in the second example would give an error in that case as well as making the code more explicitly self documenting. I have also removed the square brackets as they are not required and I find them distracting. For reasons of personal preference I have replaced the 1 with a *. It makes no difference to the execution plan.

Other changes.

I used a CTE to remove some of the repeated formulas scattered around the code.
I replaced your use of SUM()/COUNT(*) with AVG
It is only necessary to cast one of the operands to avoid integer division - not both.
I changed the column names returned by the query so they meet the rules for standard identifiers and don't need to be quoted.
I changed to the non standard column_alias = expression syntax as I find it makes the query easier to read when the select list contains long expressions.

WITH CTE
     AS (SELECT AtDateTime,
                /*Use CASE if < SQL Server 2012*/
                IIF(NumFound = 0, 1, 0)       AS NoResults,
                DATENAME(WEEKDAY, AtDateTime) AS WeekDayName,
                DATEPART(WEEKDAY, AtDateTime) AS WeekDayNumber
         FROM   dbo.SearchHistory sh
         WHERE  NOT EXISTS (SELECT *
                            FROM   dbo.CustomerExclusions ce
                            WHERE  ce.CustomerNumber = sh.CustomerNumber
                                   AND ce.ExcludeFromSearch = 1))
SELECT WeekDayName,
       NumberOfSearches
             = COUNT(*),
       AverageSearchesPerDay
             = COUNT(*) / CAST(COUNT(DISTINCT CONVERT(DATE, AtDateTime)) AS DECIMAL(10, 2)),
       NumberOfSearchesWithNoResults
             = SUM(NoResults),
       PercentOfSearchesWithNoResults
             = CAST(AVG(CAST(NoResults AS DECIMAL(10, 2))) AS DECIMAL(10, 4))
FROM   CTE
GROUP  BY WeekDayNumber,
          WeekDayName
ORDER  BY WeekDayNumber


Forecasts for construction equipment dealers I was wondering if it is possible to speed up this script? The source file has 90,000 rows, and it has to create a separate forecast for 1200 unique dealers using fbprophet. I'm new to python so I'm not sure if there is something obvious I'm missing, or if it's just going to have to take a really long time. If any sees a simple solution that would speed it up, I would appreciate any insight. Thank you
Additional details about code:
The code takes a CSV file that has 3 columns(Month, Dealer, and Sales) and creates a filter essentially for each unique dealer name, and then uses Fbprophet to forecast the future results of each dealer. Then it combines all the information in a CSV file. It's 90,000+ rows of data typically, and normally 1200 unique dealers that need to be forecasted. The historical data is 7 years of history.
from pandas import read_csv
from pandas import to_datetime
from pandas import DataFrame

from fbprophet import Prophet
from matplotlib import pyplot
import pandas as pd
# load data
data = read_csv('X.csv', header=0)
# prepare expected column names
data.columns = ['ds','Dealer', 'y']
data['ds']= to_datetime(data['ds'])

results = pd.DataFrame()

for dealer in data['Dealer'].unique():
    df_filtered = data[data['Dealer']==dealer]
    prophet_df = df_filtered[['ds', 'y']]
    # define the model
    model = Prophet()
    # fit the model
    model.fit(prophet_df)
    # define the period for which we want a prediction
    future = list()
    for h in range(11, 13):
        date = '2020-%02d' % h
        future.append([date])
    for i in range(1, 13):
        date = '2021-%02d' % i
        future.append([date])
    for j in range(1, 13):
        date = '2022-%02d' % j
        future.append([date])
    for k in range(1, 13):
        date = '2023-%02d' % k
        future.append([date])
    future = DataFrame(future)
    future.columns = ['ds']
    future['ds']= to_datetime(future['ds'])
    # use the model to make a forecast
    forecast = model.predict(future)
    forecast['Dealer'] = dealer
#     forecast.head(5)
    results = results.append(forecast)

results.to_csv('X1.csv')

Link to Sample Data: https://docs.google.com/spreadsheets/d/1lrkRQ9juDm7WZahsPV8oq2Rh7UFlFxCDpP4AgiTxTzU/edit?usp=sharing

Took some work but got a 25-30% speedup (down from roughly 5.2 to 3.8 seconds) on the sample data you provided along with cleaner code. I'm hoping that when you scale it across the full data the gains will be larger but tbd
So what are the changes?

Move whatever possible outside loops. Your future value never changes but you recreate it (relatively inefficiently) and do other DataFrame manipulation every loop which would be 1,200 times total. Not the biggest drain but it's there.

List comprehension can be a bit faster than going through regular loops and multiple assignments. Everything I could pull into a single function like pd.read_csv or pd.date_range or list comprehension I did

Slightly faster Dataframe filtering by setting df.index = "dealer" and using df.loc[np.in1d(df.index, dealer)][['ds', 'y']]. If you really want to squeeze out performance that's the fastest way I can find but probably not worth the hit to readability in normal code. Still, I left it in.

Are those three improvements? Sure. They'll add up over enough data but they're still shaving fractions of a second off. The real resource killer is Prophet doing the modeling/forecasting itself which leads to

Parallelizating Prophet with multiprocessing.Pool.imap. Instead of a loop creating the future range and then the filtering and then modeling and forecasting the data for each unique dealer now it's going to utilize multiple processors to work on each forcast more-or-less simultaneously. Probably not all 1,200 at once but more than 1. That's what accounts for most of the speedup and why hopefully you'll get even larger gains like maybe 2-4x (that's very loose guess, no promises) on the full data.

Rewrite:
from fbprophet import Prophet
import pandas as pd
import numpy as np
from multiprocessing import Pool, cpu_count

def forecast_data(args):
    (df, dealer, dates) = args

    model = Prophet()
    model.fit(df.loc[np.in1d(df.index, dealer)][['ds', 'y']])

    return model.predict(dates)

if __name__ == "__main__":
    df = pd.read_csv('X.csv', header=0, names=['ds', 'dealer', 'y'],
                     parse_dates=['y'], index_col="dealer")

    date_range = pd.date_range('2020-11', '2024-12', freq='MS')
    date_range = pd.DataFrame(date_range, columns=['ds'])

    p = Pool(cpu_count())

    results = pd.concat(
        [result for result in p.imap(
            forecast_data,
            [(df, dealer, date_range) for dealer in df.index.unique()]
        )])

    results.to_csv('X2.csv')

P.S. If you wonder why forecast_data takes a tuple and unpacks it it's because I tried to write a memoized factory function that took df and dates are arguments and returned forecast(dealer) but that caused multiprocessing to have a pickle about using a local pickle.


Determining if there is a route between two nodes in a directed graph This algorithm should return a boolean value, telling if there is a path between two nodes in a given directed graph.

public enum State{
    White, Grey;
}

public class Node {
    State state = State.White;
    List<Node> neighbors = new ArrayList<Node>();
    //Assumption: Every node already knows about its direct adjacents
    public List<Node>getAdjacent(){ return neighbors;}
}

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst))return true;

        }
    }
    return false; //NO path found
}

What do you think about the concept of it? What are the advantages of of an iterative solution?

You don't reset the src.state when you return the result.

This means that between isThereAPath calls you need to reset the state manually. Instead you should reset the state:

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                src.state = State.White;
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst)){
                src.state = State.White;
                return true;
            }

        }
    }
    return false; //NO path found
}


AVX512 - Add two 512-bit integers using _addcarryx_u64 function My purpose is to add two __m512i variables (c = a + b) as efficiently as possible. To do so, I'd like to use the _addcarryx_u64 function which takes uint64_t as inputs.

unsigned char _addcarryx_u64 (unsigned char c_in,
                              unsigned __int64 a,
                              unsigned __int64 b,
                              unsigned __int64 * out)

I manage to obtain a working function based on buffers:

__m512i _m512_add(const __m512i a, const __m512i b)
{
    const size_t n = sizeof(__m512i) / sizeof(uint64_t);
    uint64_t buf_a[n], buf_b[n], buf_c[n];

    _mm512_storeu_si512((__m512i *)buf_a, a);
    _mm512_storeu_si512((__m512i *)buf_b, b);

    unsigned char c_in = 0;

    for (unsigned i = n-1; i < n; --i)
        c_in = _addcarryx_u64(c_in, buf_a[i], buf_b[i], &(buf_c[i]));

    return _mm512_setr_epi64(buf_c[0], buf_c[1], buf_c[2], buf_c[3],
                             buf_c[4], buf_c[5], buf_c[6], buf_c[7]);
}

But it is not as efficient as I expected. Note that I compare timing and result with the GMP library and another function (based on intrinsics functions but not _addcarryx_u64) that I previously wrote.

My question is the following, is there a more efficient way to access the different uint64_t than using some buffers?
I was thinking like a table (a[i]) or using extraction functions but didn't find anything satisfying my needs / didn't manage to do it.

Probably not what you're expecting, but it's possible to do a 512-bit add directly with AVX512 registers. The _addcarryx_u64() intrinsic is not necessary nor do you need to break up the register into scalars.

Taken from my blog: http://www.numberworld.org/y-cruncher/internals/addition.html#ks_add

The following is a little-endian 512-bit full-adder:

__m512i add512(uint32_t& carry, __m512i A, __m512i B){

    const __m512i MAX_WORD = _mm512_set1_epi64(0xffffffffffffffff);

    __m512i s = _mm512_add_epi64(A, B);
    __mmask16 c = _mm512_cmplt_epu64_mask(s, A);
    __mmask16 m = _mm512_cmpeq_epi64_mask(s, MAX_WORD);

    {

        uint32_t c0 = _mm512_mask2int(c);
        uint32_t m0 = _mm512_mask2int(m);
        carry += m0;
        carry = (carry + c0*2); //  lea
        m0 ^= carry;
        carry >>= 8;
        m = _mm512_int2mask(m0);

    }

    return _mm512_mask_sub_epi64(s, m, s, MAX_WORD);
}

The carry parameter indicates the carry-in. It will be replaced with the carry-out. It must be either 0 or 1.

To clarify, this is little-endian across all 512 bits. So carry propagation goes from lowest address to highest address. I'm not sure if this is what you really wanted since your example seems to do it in big-endian with 64-bit granularity.

If you really do want this in big-endian, you will need to shuffle all the inputs and outputs since there's no way to efficiently reverse the direction of the carry-propagation.

Background:

This is something I attacked back in January of 2017 while I was experimenting with parallel adder algorithms. And somewhat by chance I managed to derive the general approach to the above method.

I've since been told that this sequence was already known internally to Intel, but they never published it. And it seems quite likely that the kadd mask instructions were specifically designed for parallel-prefix algorithms like the adder given here.


Function returning higher order function For the below given exercise:

  Define a function cycle which takes in three functions as arguments: f1, f2, f3. cycle will then return another function. The returned fuction should take in an integer argument n and do the following:

  return a function that takes in an argument x and does the following:

  if n is 0, just return x

  if n is 1, apply the first function that is passed to cycle to x

  if n is 2, the first function passed to cycle is applied to x, and then the second function passed to cycle is applied to the result of that (i.e. f2(f1(x))).

  If n is 3, apply the first, then the second, then the third function (i.e. f3(f2(f1(x))))

  if n is 4, apply the first, then the second, then the third, then the first function (i.e. f1(f3(f2(f1(x)))))

  And so forth

  Hint: most of the work goes inside the most nested function.

def cycle(f1, f2, f3):
    """ Returns a function that is itself a higher order function
    >>> add1 = lambda x: x+1
    >>> times2 = lambda x: 2*x
    >>> add3 = lambda x: x+3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1) # semanitcally the same as times2(add1(1))
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2) # semantically the same as add3(times2(add1(2)))
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2) # semantically the same as add1(add3(times2(add1(2))))
    10
    >>> do_two_cycles = my_cycle(6) # semantically the same as add3(times2(add1(add3(times2(add1(1))))))
    >>> do_two_cycles(1)
    19
    """

    " *** YOUR CODE HERE *** "

Here is the solution:

def cycle(f1, f2, f3):
    """ Returns a function that is itself a higher order function
    >>> add1 = lambda x: x+1
    >>> times2 = lambda x: 2*x
    >>> add3 = lambda x: x+3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1) # semanitcally the same as times2(add1(1))
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2) # semantically the same as add3(times2(add1(2)))
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2) # semantically the same as add1(add3(times2(add1(2))))
    10
    >>> do_two_cycles = my_cycle(6) # semantically the same as add3(times2(add1(add3(times2(add1(1))))))
    >>> do_two_cycles(1)
    19
    """
    def f(n):
        tple = (f1, f2, f3)
        def g(x, count = n):
            if count == 0:
                return x
            else:
                return g(tple[(n-count)%3](x), count-1)
        return g
    return f

My question:

The above solution is written in the functional paradigm. Please let me know if the code style breaks the functional paradigm.
Can the code be optimized without default valued second parameter of function g and tuple tple?

Note: In python, I do not like lambda and decorators

That's a pretty good solution to a tricky exercise.  I recommend two simplifications:

The definition of tple can be lifted out of f into cycle itself, as it never changes.
The code would be simpler if you count up instead of down.

def cycle(f1, f2, f3):
    tple = (f1, f2, f3)
    def f(n):
        def g(x, count = 0):
            if count == n:
                return x
            else:
                return g(tple[count % 3](x), count + 1)
        return g
    return f

As you observed, your g function is a leaky abstraction: it is supposed to take just an x argument, but it's possible to interfere with its proper behaviour by also passing it a count.  Here is one solution that avoids that problem ("apply f1, then move f1 to the end of the queue").

def cycle(f1, f2, f3):
    def f(n):
        def g(x):
            if n == 0:
                return x
            else:
                return cycle(f2, f3, f1)(n - 1)(f1(x))
        return g
    return f


Speeding up Access query with a calculated field calling a VBA function At work I have a Microsoft Access database of employees with fields such as employee's manager, employees email, and employee ID. My duties include updating this database and validating entries generated. Biweekly when I run the VBA script to validate records, I am faced with between 25K and 30K of employee records in the table. A typical validation function in VBA is below:

Public Function validateEmployeeManager(empID As String, empStatus as String, empManager As String)

    If ((empStatus = "Active") And isNull(empManager)) Then
        validateEmployeeManager = "Manager is invalid for employee" & " " & empID
    Else
        validateEmployeeManager = "Valid manager"
    End If

Calling the above in a calculated field in a query:

validateEmployeeManager([Employee_Name],[Employee_Status],[Employee_Manager]

I have noticed code such as the above takes quite a bit of time to run and display the results, given the size of the database.

Is there a more efficient method of running this validation?

Why don't you just put it in the query:

Query for employees with invalid managers:

Select [Employee_Name],[Employee_Status],[Employee_Manager]
FROM employees
WHERE [Employee_Status] = 'Active' AND isNull([Employee_Manager])

Query for employees with valid managers:

Select [Employee_Name],[Employee_Status],[Employee_Manager]
FROM employees
WHERE NOT ([Employee_Status] = 'Active' AND isNull([Employee_Manager]))

Query with the column displaying if the manager is valid or invalid

Select [Employee_Name],[Employee_Status],[Employee_Manager],
Iif([Employee_Status] = 'Active' AND isNull([Employee_Manager]), 'Invalid', 'Valid') as [Manager for employee]
FROM employees


Better way to write this code in functional manner using map and reduce? I have an array of items on which I have to perform 2 tasks:

Applying  a function on the array item
Checking if the value is true or false.

The functional approach to solving this would be

var result = arr.map(function(item){return some_action(item);}).filter(function(item){return other_action(item) == true;});

But here the array arr is traversed twice in comparison to

var result = [];
arr.forEach(function(item){
    var x = other_action(some_action(item));
    if (x)
        result.push(x);
});

Isn't the functional approach bad in this case or am I not using map and filter the right way?

Your “functional” approach is overly complicated. Notice that this is completely equivalent:

var result = arr.map(some_action).filter(other_action);

I.e. If you're only delegating to another function, you can specify that function directly. Also, an == true test is superfluous.

Your “procedural” variant is not equivalent, that would have to be:

var result = [];
arr.forEach(function(item){
    var changedItem = some_action(item);
    if (other_action(changedItem))
        result.push(changedItem);
});

Note that both variants have the same algorithmic complexity, and that the cost of iteration is likely negligible compared with the cost of some_action and other_action.

Functional programming does not mean unreadable code. Even if you're not just delegating to another function, you could improve formatting, e.g. to

var result = arr.map(function (item) {
  return some_action(item);
}).filter(function (item) {
  return other_action(item);
});


Program to find magic square of squares I have a program which finds, well, a magic square of squares. The problem is, it's quite slow - it processes around 50 numbers in half a second when the number range is above 40,000.

Is there any way to improve this code?

from math import floor

# checksquare checks for the possibility of a set being a magic square.
# One example of an incoming list (split for readability) is:
# [[1634],
# [15, 25, 28], [11, 27, 28], [8, 27, 29],
# [3, 28, 29], [12, 23, 31], [13, 21, 32],
# [9, 23, 32], [4, 23, 33], [3, 20, 35]]
# The square of each number in the lists of length 3
# add up to the single number in the list of length 1.
# (e.g. 15^2 + 25^2 + 28^2 = 1634)
# This function checks for this possibility by doing so:
# If all of the numbers in the sets of 3 are repeated at least once,
# Then it outputs it to a separate file.
def checksquare(listin):
    # listcheck only contains the lists of length 3.
    listcheck = listin[1:]
    # dictofnos is used to check the amount of each number in listcheck.
    dictofnos = {}
    # setof0s is used to remove numbers which are not repeated.
    setof0s = []
    # The first loop checks the amount of each number in listcheck.
    for e in range(len(listcheck)):
        for f in range(3):
            try:
                dictofnos[(listcheck[e])[f]] += 1
            except KeyError:
                dictofnos[(listcheck[e])[f]] = 1
    # The second loop removes any value that is not repeated.
    for g in dictofnos:
        if dictofnos[g] == 1:
            for h in range(len(listcheck)):
                if g in listcheck[h]:
                    for j in range(3):
                        if dictofnos[(listcheck[h])[j]] == 0:
                            pass
                        dictofnos[(listcheck[h])[j]] -= 1
                    listcheck.remove(listcheck[h])
                    listcheck.append([])
            for i in range(len(listcheck)):
                if len(listcheck[i]) != 3:
                    listcheck.remove(listcheck[i])
    # This if/elif is used to catch any lists that passed the two loops
    # while having non-repeating numbers.
    if 0 in dictofnos.values():
        [setof0s.append(k) for k in dictofnos if dictofnos[k] == 0]
    elif 1 in dictofnos.values():
        listcheck = listin[:1] + listcheck
        checksquare(listcheck)
        return None
    # The final loop is deleting entries in the dict which are removed
    # (hence the use of setof0s).
    for l in setof0s:
        del dictofnos[l]
    # Outputs to output.txt.
    if len(listcheck) != 0:
        output = open("output.txt", "a+")
        output.write("\n" + str(listin[0]) + "\n" + str(dictofnos) + "\n" + str(listcheck) + "\n")
        output.close()

# powers checks if 3 squares add up to a number.
def powers(limit):
    numberrange = 3 * ((limit + 1) ** 2)
    for a in range(numberrange):
        # Everything here is for efficiency.
        temp = 0
        templist = [[a]]
        check = 1
        b = 0
        c = int(floor((a / 4.0) ** 0.5))
        d = int(floor((a / 2.0) ** 0.5))

        while b <= c <= d <= limit and d ** 2 < a:
            b += check
            if b == c or (b * 2) ** 2 > a:
                c += 1
                b = 1
                continue
            if c == d:
                d += 1
                c = int(floor((a / 4.0) ** 0.5))
                b = 1
                continue
            if (b + c + d) % 2 != a % 2:
                check = 2
                b -= 1
                continue
            if b ** 2 + c ** 2 + d ** 2 == a:
                templist.append([b, c, d])
                temp += 1
        # If 8 solutions for b^2 + c^2 + d^2 = a are found
        # for any a, then it is sent to checksquare.
        if temp >= 8:
            checksquare(templist)

# The usage of these functions would be to put
# powers(whatever the upper bound of d is).
powers(100)

EDIT: Added explanation (sorry if it's really long), and improved some minor things.

This is at least a start. I did not look very heavily in finding a better algorithm itself, just making small improvements of you algorithm. Nevertheless this resulted in a speed-up of about 30%.

For comparison (I changed the call to powers(50) so it does not take so long):

# Your code
$ python -m cProfile magic_square_orig2.py
         81524 function calls in 3.462 seconds
# With the changes below
$ python -m cProfile magic_square2.py
         18110 function calls (18107 primitive calls) in 2.496 seconds

With powers(75):

# Your code
$ python -m cProfile magic_square_orig2.py
         336810 function calls in 30.210 seconds
# With the changes below
$ python -m cProfile magic_square2.py
         148883 function calls (148880 primitive calls) in 18.832 seconds

Use better names (!!)

Even now, where you changed some variable names for better names, the function checksquare is very hard to understand because of variables called g, h, j, k. But since I will take away their meaning as integers below, anyways, we can find better names for them.

Iterate over the contents of a list

It is always easier to iterate over the list, instead of iterating an index, compare:

for i in range(len(l)):
    print l[i]
for element in l:
    print element

The latter is a lot easier to read (and understand). It is the recommended way to iterate over a list. So I changed your logic and gave the variables better names:

Use collections.Counter()

There is already an existing construct that builds a dictionary with counts of objects, it is callen collections.Counter. This way you can replace:

for e in range(len(listcheck)):
        for f in range(3):
            try:
                dictofnos[(listcheck[e])[f]] += 1
            except KeyError:
                dictofnos[(listcheck[e])[f]] = 1

with:

from collections import Counter
...
dictofnos = Counter(item for sublist in listcheck for item in sublist)

Use list comprehensions where possible

List comprehensions are in general faster than manually writing the for loop, because they are implemented in C (they are not, see e.g. here) a more succinct way to write simple loops that build a list. You can replace some loops:

for i in range(len(listcheck)):
                if len(listcheck[i]) != 3:
                    listcheck.remove(listcheck[i])

becomes one of these two:

listcheck = filter(lambda powers: len(powers) == 3, listcheck)
listcheck = [powers for powers in listcheck if len(powers) == 3]

which seem to be about the same speed. where the latter should be slightly faster, because the filter has to take a lambda instead of a predefined function. But using the fact that the only two possible lengths are 0 and 3 and bool(0) == False and bool(3) == True we can just use

listcheck = filter(len, listcheck)

in this case.

function powers

You compute for example b**2 more than once. It saves quite some time if you save b2 = b**2 (and similar for the other variables) at appropriate places.

int() already performs floor so it is not needed here. (int(3.14) == 3 and int(3.99) == 3)

You can collect what to write to the output file and write it in one go. This should be faster than repeated opening, writing and closing of the file. For this the function checksquare needs to be adapted to return the values instead of writing it:

if listcheck:
        return listin[0], dictofnos, listcheck

and in powers we add a list to collect the return values:

def powers(limit):
    out = []
    ....
        if temp >= 8:
                squares = checksquare(templist)
                if squares:
                    out.append(squares)
    ....
    return out

Additionally, we can put the writing part to a new function, separating the calculation and output part:

def write_powers(n):
    with open("output2.txt", "w") as out_file:
        for power in powers(n):
            out_file.write("\n{}\n{}\n{}\n".format(*power))

This also guarantees that the file will be overwritten with each subsequent call to the script ("w" writes, over-writing the file, while you "a+" was always appending).

Misc

Use the __name__ hook in order to allow importing you function from another script without executing powers(75) every time:

if __name__ == "__main__":
    write_powers(75)

Use an actual set for setof0s.

Result

from collections import Counter

def checksquare(listin):
    # listcheck only contains the lists of length 3.
    listcheck = listin[1:]
    # dictofnos is used to check the amount of each number in listcheck.
    dictofnos = Counter(factor for factors in listcheck for factor in factors)
    # setof0s is used to remove numbers which are not repeated.
    setof0s = set()
    # The first loop checks the amount of each number in listcheck.
    # The second loop removes any value that is not repeated.
    for factor in dictofnos:
        if dictofnos[factor] == 1:
            for factors in listcheck:
                if factor in factors:
                    for power in factors:
                        if dictofnos[power] == 0:
                            pass
                        dictofnos[power] -= 1
                    listcheck.remove(factors)
            #listcheck = filter(lambda powers: len(powers) == 3, listcheck)
            listcheck = [powers for powers in listcheck if len(powers) == 3]
    # This if/elif is used to catch any lists that passed the two loops
    # while having non-repeating numbers.
    if 0 in dictofnos.values():
        setof0s |= set(k for k in dictofnos if dictofnos[k] == 0)
    elif 1 in dictofnos.values():
        listcheck = listin[:1] + listcheck
        checksquare(listcheck)
        return
    # The final loop is deleting entries in the dict which are removed
    # (hence the use of setof0s).
    for l in setof0s:
        del dictofnos[l]
    # Outputs to output.txt.
    if listcheck:
        return listin[0], dict(dictofnos), listcheck

# powers checks if 3 squares add up to a number.
def powers(limit):
    out = []
    numberrange = 3 * ((limit + 1) ** 2)
    for a in range(numberrange):
        # Everything here is for efficiency.
        temp = 0
        templist = [[a]]
        check = 1
        b = b2 = 0
        c = int((a / 4.0) ** 0.5)
        d = int((a / 2.0) ** 0.5)
        c2, d2 = c**2, d**2

        while b <= c <= d <= limit and d2 < a:
            b += check
            b2 = b**2
            if b == c or 4*b2 > a:
                c += 1
                c2 = c**2
                b = b2 = 1
                continue
            if c == d:
                d += 1
                d2 = d**2
                c = int((a / 4.0) ** 0.5)
                c2 = c**2
                b = b2 = 1
                continue
            if (b + c + d) % 2 != a % 2:
                check = 2
                b -= 1
                b2 = 1
                continue
            if b2 + c2 + d2 == a:
                templist.append([b, c, d])
                temp += 1
        # If 8 solutions for b^2 + c^2 + d^2 = a are found
        # for any a, then it is sent to checksquare.
        if temp >= 8:
            squares = checksquare(templist)
            if squares:
                out.append(squares)
    return out

def write_powers(n):
    with open("output2.txt", "w") as out_file:
        for power in powers(n):
            print power
            out_file.write("\n{}\n{}\n{}\n".format(*power))

# The usage of these functions would be to put
# powers(whatever the upper bound of d is).
if __name__ == "__main__":
    write_powers(75)


Get the width and height of a shape as user input I made this program to understand inheritance better.

Now that I'm at this basic level it's not really a problem but I can see this coming in the future and so I'm asking what's the best method to ask the user to insert the width and height of a rectangle (in this case).

The code I'm providing includes the simple way, by simply asking the user and inserting the number in a variable, then passing the variable to the setter inside the object (rect1).

I think when I will add up more shapes this can become a little confusing, is there a better way I can ask the user to input the number?

Since I'm asked to provide more context:
I'm generally asking what's the best or a better method to ask input from the user that is going inside an object.

This is my version of it, that I think is good in this simple level but it will get messy with more shapes or generally more classes, I use 2 variable to ask for 2 dimensions, I will need 1 variable for every dimension and when I will create an object if I pass the wrong variable the program will work anyway, giving the wrong result.

Another way that I thought is insert an "askSomething" method in each class so that I don't need variables and every time a new object is created the io stream will be asked automatically.
The "AskSomething" method is identical to a setter except it has cout and cin already inside

I don't really came up with other ideas.

The code I'm providing is a simple program that by asking height and width of a Rectangle calculate its Area, but of course by the class name Rectangle, the member names height and width and the method name getArea was pretty obvious.

main.cpp:

int main() {
    Rectangle rect1;
    int width, height;

    std::cout << "Insert the width of the rectangle: ";
    std::cin >> width;

    std::cout << "Insert the height of the rectangle: ";
    std::cin >>height;

    rect1.setHeight(height);
    rect1.setWidth(width);

    std::cout << "The area of the rectangle is: " << rect1.getArea() << std::endl;

    std::cout << "Drawing: " << std::endl;
    std::cout << " ";
    for (int i = 0; i < width+1; ++i) {
        std::cout << "-";
    }
    std::cout << std::endl;
    for (int j = 0; j < (height+1)/2; ++j) { // divided by 2 to have a better proportion
        std::cout << "|";
        for (int i = 0; i < width+1; ++i) {
            std::cout << " ";
        }
        std::cout << "|";
        std::cout << std::endl;
    }
    std::cout << " ";
    for (int i = 0; i < width+1; ++i) {
        std::cout << "-";
    }

    return 0;
}

Shape.h:

class Shape {
public:
    int getWidth() const {
        return width;
    }

    void setWidth(int width) {
        Shape::width = width;
    }

    int getHeight() const {
        return height;
    }

    void setHeight(int height) {
        Shape::height = height;
    }

protected:
    int width, height;
};

Rectangle.h:

class Rectangle: public Shape {
public:
    int getArea(){
        return width*height;
    }
};

Thanks to everyone! :)

I think you have chosen really bad way to model the inheritance relation between a rectangle and a shape.

I believe that every shape has an area. Unlike your Shape class, which does not allow this, only the Rectangle class does.

On other hand, I believe that not all shapes have width and height. If anything, they have a smallest outer rectangle which has a width and height. Unlike, your Shape class which always has width and height and allows to set it to any arbitrary value.

You should turn it inside out.

You can still have the shape be able to give you the smallest outer rectangle (with its width and height), but implementing that method for anything except the Rectangle (where it would just return copy of itself) would be a bit more complex and providing such code for you would go far beyond a code review :) But that way you can provide the width/height pair in a read only manner, making sure that it cannot be modified for shapes where it would lead to corruption (like setting width!=height for a circle).

I would also rather use double for the numeric values as you would soon find out that areas of shapes are not always integers even for shapes which themselves are defined with integers (although this is not the case for rectangles).

class Rectangle;

class Shape
{
public:
  virtual ~Shape() {}
  virtual double getArea() const = 0;
  virtual Rectangle getSmallestOuterRectangle() const = 0;
};

class Rectangle : public Shape
{
public:
  double width, height;

  Rectangle(double width, double height) : width(width), height(height) {}
  virtual ~Rectangle() {}
  virtual double getArea() const {return width * height;}
  virtual Rectangle getSmallestOuterRectangle() const {return *this;}
};

Further obviously, you cannot create all shapes from just height and width.
If I wanted to create a circle, two variables are too much.
If I wanted to create an arbitrary triangle, two variables are not enough.

In any way, having the Shape/Rectangle/Circle/Triangle classes know anything about streams is a mistake. You can always read the values into variables and pass them through constructor or update the respective property (if you made them public, which is ok here I believe, no setters/getters are needed).


Kadane's Algorithm, finding maximum contiguous array Description of Kadane's algorithm.
Please comment on the efficiency and approach.

class Kadane {
int sum = 0;
int max = 0;

public static void main(String[] args) {
    int[] full = { 1, 2, 3, 4, 5, -6, -77, 3, 14, -10 };
    Kadane Kadane = new Kadane();
    int max = Kadane.splitArr(full);
    System.out.println("The maximum value of the seq is " + max);
}

public int localMax(int[] full, int sublength) {
    for (int i = sublength; i >= 0; i--) {
        sum = sum + full[i];
        if (sum > max) {
            max = sum;
        }
    }
    sum = 0;
    return max;
}

public int splitArr(int[] full) {
    int sum_final = 0;
    int max_final = 0;
    for (int j = 0; j < full.length; j++) {
        sum_final = localMax(full, j);
        if (sum_final > max_final) {
            max_final = sum_final;
        }
    }

    return max_final;
}
}

Ok, let's take a look:

Kadane Kadane = new Kadane();

If there is no need for it, I would use static methods and avoid object creation:

public static int localMax(int[] full, int sublength) {...}
public static int splitArr(int[] full) {...}
int max = splitArr(full);
//(+ next point)

int sum = 0;
int max = 0;

I do not see the reason why they are class variables? You could use them in the method scope and have 2 benefits:

You do not have any state inside your class, which makes the methods recallable.
You can be sure nobody starts to modify it somewhere.

public int localMax(int[] full, int sublength) {
    final int sum = 0;
    final int max = 0;
    //...
}

public int splitArr(int[] full)

This is a bad name. If someone reads only the method name, it is impossible to figure out what this is doing. You would expect to split an array? Then you would expect to get back one or multiple arrays. But you get an int.
A better method name could be:

public int getMaximumSumOfAllSubarraysFromArray(final int[] array)

(same goes for localMax)

Instead of:

if (sum > max) {
    max = sum;
}
//...
if (sum_final > max_final) {
    max_final = sum_final;
}

You could write:

max = Math.max(max, sum);
max_final = Math.max(max_final, sum_final);

Which makes the intention directly clear.

If we take this line:

sum_final = localMax(full, j);

You could inline the function localMax:

public int splitArr(final int[] full) {
    int sum_final = 0;
    int max_final = 0;
    for (int j = 0; j < full.length; j++) {
        int sum = 0;
        for (int i = j; i >= 0; i--) {
            sum = sum + full[i];
            sum_final = Math.max(sum_final, sum);
        }
        max_final = Math.max(max_final, sum_final);
    }

    return max_final;
}

Then we look what is happening here:

In the 1. loop iteration, we check calculate the sum from index 0 to index 0
In the 2. loop iteration, we check calculate the sum from index 1 to index 0
In the 3. loop iteration, we check calculate the sum from index 2 to index 0

We can see a pattern here. We do not have to do all the calculations from previous sums, we just use the previous result and add the new current element:

int sum = 0;
for (int j = 0; j < full.length; j++) {
    sum = sum_final + full[i];
    sum_final = Math.max(0, sum);
    max_final = Math.max(max_final, sum_final);
}

Good thing: We got rid of the O(n^2) complexity back to O(n).
Good thing: we can simplify it even more. The variable sum is not necessary and we can use a foreach:

public int splitArr(final int[] full) {
    int sum_final = 0;
    int max_final = 0;
    for (final int element : full) {
        sum_final = Math.max(0, sum_final + element);
        max_final = Math.max(max_final, sum_final);
    }
    return max_final;
}

We can choose some better names for all the variables and if we apply all the mentioned things we could end up with:

public static int getMaximumSumOfAllSubarraysFromArray(final int[] array) {
    int currentMaximum = 0;
    int overallMaximum = 0;
    for (final int arrayItem : array) {
        currentMaximum = Math.max(0, currentMaximum + arrayItem);
        overallMaximum = Math.max(overallMaximum, currentMaximum);
    }
    return overallMaximum;
}

(which is by the way the same algorithm as mentioned from the Wikipedia link, and I think the best one for single thread, typical environments. It could be improved by removing the first Math.max, merging the branches and saving a little part of branching, but this would reduce readability):

public int getMaximumSumOfAllSubarraysFromArray(final int[] array) {
    int currentMaximum = 0;
    int overallMaximum = 0;
    for (final int arrayItem : array) {
        currentMaximum = currentMaximum + arrayItem;
        if (currentMaximum > 0)
            overallMaximum = Math.max(overallMaximum, currentMaximum);
        else
            currentMaximum = 0;
    }
    return overallMaximum;
}

One last piece of advice: If you develop such algorithms and refactor them, you should always have some unit tests for this. Better more than less.

I hope you can combine this hints to a full working approach. If not, just mention the flaws in my descriptions.


Implementation of a quicksort function I am an absolute beginner to programming and am learning it using C. I have just learned function pointers and tried to implement a quicksort function using function pointers to determine the nature of sorting.

//Program implementing a quick-sort function using Hoare method
//to partition using a random pivot.
//Function pointer is used to determine the nature of sort (Ascending / Descending).
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

//Typedef: Function Pointer to be used for determining he nature of sort:
typedef int (*p_compare_function)(long long,long long);

enum BOOLEAN{FALSE,TRUE};

//FUNCTION PROTOTYPES:

//Functions to be used for determining the nature of sort:
int Ascending   (long long x,long long y);
int Descending  (long long x,long long y);

//Generates a random number between a lower and a upper limit.
long long my_random(long long min, long long max);

//Functions to be used for the actual functioning of the algorithm:
void my_swap(long long* a, long long* b);

long long quicksort_partition(  long long* array, long long begin,
                                long long end, p_compare_function cmp);

void quicksort( long long* array, long long begin, long long end,
                p_compare_function cmp);

void printarray(long long *pArray, long long nSize);

int main() {

    srand(time(NULL));

    long long array[] = {5,2,9,7,3,1,6,8,4,0,4,3,5,67,22,3,644,335,345,24,
                         33,25,22,5,2,43223,4};

    long long arraysize = sizeof(array)/sizeof(*array);

    //Testing
    quicksort(array,0,arraysize-1,Ascending);
    printarray(array,arraysize);

    quicksort(array,0,arraysize-1,Descending);
    printarray(array,arraysize);

    return 0;
}

void printarray(long long *pArray, long long nSize) {
    for (long long i=0; i < nSize; i++) {
        printf("%lld ",pArray[i]);
    }
    printf("\n");
}

int Ascending   (long long x,long long y) {
    if (x < y) {
        return TRUE;
    }
    else {
        return FALSE;
    }
}

int Descending  (long long x,long long y) {
    return ( !(Ascending(x,y)) );
}

long long my_random(long long min, long long max) {
    long double result;
    result = ((double)rand() / ((double)RAND_MAX + 1.0));
    result = (result * (max - min));
    result += min;
    result = (long long) result;
    return result;
}

void my_swap(long long* a, long long* b) {
    long long temp = *a;
    *a = *b;
    *b = temp;
}

long long quicksort_partition(  long long* array, long long begin,
                                long long end, p_compare_function cmp) {

    //Randomly selecting the pivot.
    long long random_index  = my_random(begin,end);
    long long pivot;
    my_swap(&array[begin],&array[random_index]);
    pivot = array[begin];

    //Partion matheod used : Hoare partition.
    long long i  = begin - 1;
    long long j  = end   + 1;

    while(TRUE) {
        do {
            j--;
        } while (!(cmp(array[j],pivot)) && array[j] != pivot);

        do {
            i++;
        }while ((cmp(array[i],pivot)) && array[i] != pivot);

        if (i < j) {
            my_swap(&array[i],&array[j]);
        }
        else {
            return j;
        }
    }
}

void quicksort(long long* array, long long begin, long long end, p_compare_function cmp) {

    if (begin < end) {
        long long q = quicksort_partition(array, begin, end, cmp);
        quicksort(array, begin  , q, cmp);
        quicksort(array, (q + 1),  end   , cmp);
    }
}

Please point out the bad practises used here and help me to rectify them.

Definitions

//FUNCTION PROTOTYPES:

Given that you have everything in one file, you could simply change the declaration order and get rid of these.  Function prototypes are necessary only when you are linking multiple files together (or in the odd case of two or more functions that call each other circularly).  They are overkill here.

int Ascending   (long long x,long long y);
int Descending  (long long x,long long y);

While the compiler won't care, adding spaces between the function name and the parameters list makes this look like something other than a function to me.  I.e. I find this notation confusing.

main

long long arraysize = sizeof(array)/sizeof(*array);

There is a type explicitly for handling size data.  You may think that you are being more inclusive by using long long, but you are actually moving errors from where the problem occurs to where clipping occurs.  In programming, it is generally better to be consistent than right.  Because even if you are more right, you will be wrong in your interactions.

size_t array_count = sizeof(array) / sizeof(*array);

The size_t type is what is used in library functions dealing with sizes.  Using it here means that if you add an additional sort that does a malloc, that you will be using the right type.

I also changed the name of the variable.  One, because I prefer the name count for something that represents the number of elements in a collection.  Two, because words should be separated by something.  In C, the standard is to use underscores.  In other languages, they often use casing to indicate where new words begin (I disagree with that actually, but at least it is common).  It's much easier to read if you use something to say where new words begin.  Otherwise, the reader has to think about it when we want the reader's attention on what the code is doing.

Similarly, I added spaces around the /.  This makes it easier to see where one token ends and another begins.

I didn't change it here, but I would prefer a name like data or sample_data instead of array.  I can easily see the type of the variable.  What I want to know is what it represents.  Thus, sample_data or test_data would best tell me what I wouldn't otherwise know from the declaration.

quicksort(array,0,arraysize-1,Ascending);

Again, I'd find this easier to read with more spacing.

quicksort(array, 0, array_count-1, Ascending);

You could also add spaces in array_count - 1, but it's not strictly necessary.

my_random

    result = (long long) result;

This does a double cast.  Since result is a long double, this casts to long long and then back to long double.  Presumably that's not what you wanted.  Instead, use a different variable on the left hand side.  Note that you should probably add min after the cast rather than before.

Your max value is inclusive, meaning that it's a valid result from this function.  However, you add 1.0 to MAX_RAND which makes it exclusive of the upper bound.  I.e. result will never be 1.0.  This seems incorrect.

You also just cast from floating point to integer, which drops the fractional part.  This will tend to bias the result down.

size_t my_random(size_t min, size_t max) {
    long double intermediate;
    size_t result;

    intermediate = (double)rand() / (double)RAND_MAX;
    intermediate *= max - min;

    result = (size_t) (intermediate + .5);
    result += min;

    return result;
}

Now it's clear where we are doing casts.  We have a declarations section, a floating point section, an integer section, and a return section.  We do only one implicit cast (to max - min which is cast to long double by the multiplication).  All other operations are done with variables that are already of the same type.

I still have one problem with this.  It's quite possible for max - min to be larger than RAND_MAX.  If that happens, there are some potential pivots that we'll never pick.

Also, this function is not robust if max < min.  In that case, the results could be weird.

quicksort

    quicksort(array, begin  , q, cmp);
    quicksort(array, (q + 1),  end   , cmp);

If you are going to do this, please keep the commas with the token before them:

    quicksort(array, begin,   q,   comparison_function);
    quicksort(array, (q + 1), end, comparison_function);

Also note that the spacing between end and cmp was simply wrong.

I also renamed cmp to comparison_function here.  Given how little it's used, it seemed better to favor readability over convenience here.  This is what Larry Wall calls true laziness -- commenting your code so that it's easier to read later.  In application, you will spend more time reading code than writing it.  It's only in the somewhat artificial environment of learning that you can spend more time writing code than reading it.  So it's better to get in the habit of writing readable code than terse code.

Comparing

return ( !(Ascending(x,y)) );

You define Descending as not Ascending, however this gives the two of them different meaning.  Something is Ascending if x < y but is Descending if x >= y.  Better might be

// Descending is the reverse of Ascending
return Ascending(y, x);

This is a little harder to follow but it now makes it Descending if y < x.  Another way to put this is that it is now Ascending in the opposite direction.

    }while ((cmp(array[i],pivot)) && array[i] != pivot);

This logic can also be simplified then.  Because all our comparison functions only return TRUE for a strict inequality, we don't need an extra inequality check on this one (the other is still needed).

    } while ( cmp(array[i], pivot) );

Note that qsort gets around this by demanding that the comparison functions return zero for equality and positive or negative values for inequalities.


Finding sessions associated with an IP address using PDO Originally Posted on Stack Overflow

First of all I want to say that I'm new to PDO. I did tried it once but since I found the oop solution complicated and even impossible (SELECT * FROM table_name) I decided to use PDO.

But I'm not sure if I do it right, so I'd like to take criticism about what I've done. I'm "translating" the mysqli stmt to pdo. Here's an example from one thing I've "translated":

// Client IP has been defined previously,
// But for the example:
$ip     = '3ffe:1900:4545:3:200:f8ff:fe21:67cf';
$sql_ip = inet_pton($ip); // IPV6

try {
    $stmt = $pdo->prepare('SELECT * FROM sessions WHERE s_ipv4 = :s_ipv4 OR s_ipv6 = :s_ipv6');
    $stmt->bindParam(':s_ipv4', $sql_ip);
    $stmt->bindParam(':s_ipv6', $sql_ip);
    $stmt->execute();

    if ($stmt->rowCount() === 0) {
        // No rows
    } else {
        // Do something
    }
} catch (Exception $exception) {
    die ($exception->getMessage());
}

unset($stmt);

Am I doing it right?

There are two main points of improvement:

First of all, never ever use die(error message) in your scripts. Neither try/catch should be ever used only to echo the error message out. You'd be surprised, but you will have more informative error message if just get rid of the whole try/catch/die stuff. Please read my article on PHP error reporting for the details
PDO code itself could be made more tidy, thanks to various helper functions PDO offers

So the whole code should be

$sql_ip = inet_pton($ip); // IPV6

$stmt = $pdo->prepare('SELECT 1 FROM sessions WHERE s_ipv4 = ? OR s_ipv6 = ?');
$stmt->execute([$sql_ip,$sql_ip]);

if ($stmt->fetchColumn()) {
    // Do something
} else {
    // No rows
}

Here I used positional placeholders for brevity, and sent your variables directly to execute for the same purpose.

Also I recommend to avoid rowCount() function as it would be more logical: in your code you are selecting some data, but never use it. Instead, I would suggest to use the actual data selected (just a literal "1" in your case, fetched directly using fetchColumn() method).


Methods to get single and multiple JDBC results I have two methods which are very similar apart from the method call inside and the return type. I wondered if there was a way to make it neater, i.e not duplicate the boiler plate connection code. I considered putting a flag in the method signature to switch, something like isMultiple but in the end I didn't like this and as the return type is different that won't work. I wondered if there was something nice I could do with Java 8.

Methods:

protected String getSingleFilePathResult(Query query) throws UwsException {
      JdbcPooledConnection conn = createConnection();
      try {
         return conn.getSingleFilePathResult(query);
      } catch (SQLException sqle) {
         throw new UwsException(SQL_EXCEPTION + sqle.getMessage(), sqle);
      } finally {
         closeConnection(conn);
      }
   }

protected List<String> getMultipleFilePathResults(Query query) throws UwsException {
      JdbcPooledConnection conn = createConnection();
      try {
         return conn.getMultipleFilePathResults(query);
      } catch (SQLException sqle) {
         throw new UwsException(SQL_EXCEPTION + sqle.getMessage(), sqle);
      } finally {
         closeConnection(conn);
      }
   }

You can factor out the boilerplate like so:

protected String getSingleFilePathResult(Query query) throws UwsException {
    return doWithConnection(conn -> conn.getSingleFilePathResult(query));
}

protected List<String> getMultipleFilePathResults(Query query) throws UwsException {
    return doWithConnection(conn -> conn.getMultipleFilePathResults(query));
}

protected <T> T doWithConnection(Function<conn, T> callback) throws UwsException {
    try (JdbcPooledConnection conn = createConnection()){
        return callback.Invoke(conn);
    } catch (SQLException sqle) {
        throw new UwsException(SQL_EXCEPTION + sqle.getMessage(), sqle);
    }
}


High CPU utilisation for Logs Manager shell script I have written a shell script to manage the tcpdump pcap logs and syslog files in my Linux board, so as to maintain the disk usage to maximum of 70%.

The script checks for the disk usage every minute and as soon as the disk goes higher than 70%, it deletes all the oldest files that are not in use until the disk usage goes back to 70%.

#!/bin/ash

#Gives the file that is currently in use by the process
logmgr_get_current_file_name() {
    PROC_NAME=$1
    instance=$2

    pid=$(ps | grep $PROC_NAME | grep -v grep | awk 'NR=='$instance'{print $1}')

    fds=$(ls /proc/$pid/fd)

    for fd in $fds;
    do
        last=$fd
    done

    current_file=$(ls /proc/$pid/fd/$last -l | awk 'BEGIN {FS="->"} {printf $2}')
}

#checks whether the file we are deleting is in use by the process
logmgr_is_file_in_use() {
    num_of_instances=1
    logmgr_get_current_file_name $1 $num_of_instances
    if [ $current_file = $2 ]; then
        return 1
    else
       return  0
    fi
}

# iterate through all possible instances of tcpdump
# for each instance .. get the file in use
# check if [ $file_in_use == $to_delete ] ; then
# return 1
# else
# return 0
logmgr_get_files_in_use() {
    i=1
    is_file_inuse=0

    num_of_instances=$(ps | grep tcpdump| grep -v grep | wc -l)

    while [ $i -le $num_of_instances ];
    do
        logmgr_get_current_file_name $1 $i
        if [ "$current_file" = "$2" ]; then
            is_file_inuse=1
            break
        fi
                i=`expr $i + 1`
        done
        return $is_file_inuse
}

logmgr_delete_oldest() {

    oldest=$(ls -lht $2 | awk 'END{print $9}')
    to_delete=$2$oldest

    if [ "$1" != "tcpdump" ] ; then
        logmgr_is_file_in_use $1 $to_delete
        ret_val=$?
    else
        logmgr_get_files_in_use $1 $to_delete "tcpdump"
        ret_val=$?
    fi

    #if the file is not in use, then delete it
    if [ $ret_val -eq 0 ]; then
        echo "$to_delete deleted"
        rm -fr $to_delete
        sleep $cpu_relaxation_secs
    fi

}

logmgr_get_disk_usage() {
    diskusage=$(df -h $1 | awk 'END {print $5}' | awk 'BEGIN {FS="%"} {print $1}')
    echo $diskusage
}

    ##requires repeated execution######
logmgr_run() {

    sleep_secs=0

    while [ 1 ] ;
    do
        syslog_dir_is_ok=0
        tcpdump_dir_is_ok=0

        syslog_disk_usage=`logmgr_get_disk_usage $syslog_dir`
        tcpdump_disk_usage=`logmgr_get_disk_usage $tcpdump_dir`

        if [ $syslog_disk_usage -le $NORMAL_DISK_USAGE ] ; then
            syslog_dir_is_ok=1
        fi

        if [ $tcpdump_disk_usage -le $NORMAL_DISK_USAGE ] ; then
            tcpdump_dir_is_ok=1
        fi

        if [ $syslog_dir_is_ok -eq 0 ] && [ $tcpdump_dir_is_ok -eq 0 ] ; then
            break
        fi

        if [ $syslog_dir_is_ok -eq 0 ] ; then
            num_files=`ls -lht $syslog_dir | wc -l`
            logmgr_delete_oldest "syslogd" $syslog_dir $num_files
        fi

        if [ $tcpdump_dir_is_ok -eq 0 ] ; then
            num_files=`ls -lht $tcpdump_dir | wc -l`
            logmgr_delete_oldest "tcpdump" $tcpdump_dir $num_files
        fi
    done
}

##Default values##

max_file_safe=100
cpu_relaxation_secs=1
timer_secs=60   # one minute
KEEP_CHECKING=1
NORMAL_DISK_USAGE=20

# read the configuration file
syslog_dir=`uci get syslog.slog.directory`
syslog_dir=`dirname $syslog_dir`"/"`basename $syslog_dir`"/"
tcpdump_dir=`uci get tcpdump.tcpdump.log_dir`
tcpdump_dir=`dirname $tcpdump_dir`"/"`basename $tcpdump_dir`"/"

#while [ $KEEP_CHECKING -eq 1 ]
while :
do
    logmgr_run
    sleep $timer_secs
done

The script is sequential and works perfectly fine but the CPU utilisation gets higher to about 75% while running the script. I tried to remove all the redundancies in script but still not successful in achieving the desired result.

I am sure there are ways with which I can achieve this, but am not sure how. Please suggest some ways to optimise this script and reduce my CPU utilisation.

If your CPU is rising to 75% and staying there (not bouncing up and down), then it suggest that your script is spinning and not hitting any of your sleep statements.  There's a few things that may be worth looking into.

The while loop in logmgr_run keeps going until enough files have been cleared out.  If this doesn't happen, then it'll never get to the 60 second sleep.
logmgr_delete_oldest will only sleep if it deletes a file, which only happens if the file isn't in use.

I haven't tested it, and it has been a while since I did script programming, but it looks to me like your algorithm breaks down if the oldest file in either folder is being used at the same time that you breach the usage threshold.  It can't delete the oldest file, so it just keeps trying over and over again without succeeding or sleeping.

Rather than having a loop that keeps trying to remove the last file when the threshold is breached it might be better to calculate the amount of files that need to be removed in order to come back under the threshold and try to remove several files in one go / or to skip files if they are in use and move on to the next file rather than stopping and trying the same file again next time.

It may also be worthwhile extending the cleanup to clear a bit more than you need, so that you don't immediately trigger another cleanup next time you go through the loop.  So, for example if you breach 70% usage, clear down the files to 65% or 60% so that there is some growth space.

Your script also has some declared an unused variable, which you should probably either be using (or remove):

max_file_safe=100


Chrome extension to get youtube video's URL I needed something that would get the URL of a chosen video from YouTube and store it in a file.

Since I didn't find a way to write/edit an existing file with the URL alone, I had to use a patchwork of JavaScript and bash to stitch together the complete URL.

I'm asking if there were things I could have done better or with a different approach.

Here's the code of the extension:

manifest.json:

{
    "manifest_version": 2   ,

    "name": "Adder",
    "description": "Add video's URL to file for future download",
    "version": "1.3.1",
    "icons": { "128": "icons/square_youtube.png"},
    "background": {
        "scripts": ["background.js"],
        "persistent": false
     },

     "permissions": [
        "tabs",
        "downloads",
        "declarativeContent"
    ],

    "page_action": {
        "default_name": "Adder",
        "default_icon": "icons/square_youtube.png",
        "default_popup": "popup.html",
        "default_title": "Add it!"
    }
}

background.js:

// Update the declarative rules on install or upgrade.

chrome.runtime.onInstalled.addListener(function() {
    chrome.declarativeContent.onPageChanged.removeRules(undefined, function() {
            chrome.declarativeContent.onPageChanged.addRules([{
                conditions: [
                    // When a page contains a <video> tag...
                    new chrome.declarativeContent.PageStateMatcher({
                        css: ["video"]
                    })
                ],
                // ... show the page action.
                actions: [new chrome.declarativeContent.ShowPageAction() ]
            }]);
    });
});

popup.js (popup.html just call this script):

var stripThis = "https://www.youtube.com/watch?v=";

chrome.tabs.query({active: true, lastFocusedWindow: true}, function(tabs) {
    var currentUrl = tabs[0].url;
    var smallUrl = currentUrl.substring(stripThis.length, currentUrl.length);
    var pathDL = "URLs/"+smallUrl+".txt";

    chrome.downloads.download({url: currentUrl, filename:pathDL}, function(downloadId) {});
});

Let me explain what this does in particular:

I built a panel_action extension that only shows if there is a video in the page. Then if I click on the icon in the omnibar, the extension download the WHOLE html page in a .txt file named after the videoID.

Then using a bash script I take all the names of the files and merge them in a single list.

Here's the bash script:

#!/bin/bash
DownloadAndConvert() {
    echo Avvio...
    echo Importo URLs da files...
    echo creo lista unificata...
    cd /home/faceless/Dropbox/URLs/
    count=`ls -1 *.txt 2>/dev/null | wc -l`
    YTBSTR="https://www.youtube.com/watch?v="
    if [ $count != 0 ]; then
        touch mergedList
        for filename in *.txt; do
            echo $YTBSTR$(basename "$filename" .txt) >> mergedList
            if [ $filename != mergedList ]; then
                rm $filename
            fi
        done
        download
        cleanup
    elif [ -e mergedList ]; then
        echo La lista è già presente! - Procedo...
        download
        cleanup
    else
        echo Non ci sono video! - Esco
        exit
    fi
}
download() {
    echo Inizio Scaricamento...
    youtube-dl -x -a "mergedList" --no-playlist
}

cleanup() {
    echo Pulisco lista...
    rm mergedList
    echo FINE
}

trap exit SIGINT
DownloadAndConvert

I then use another program (built exactly for this task) to download and convert as desired all the video in that list.

This system feel a lot clumsy and it is mostly a patchwork of snippets of code took here and there (especially the JavaScript ones). That's why I'm asking for insights for improvements!

In the bash script, I could most likely just use the videoID instead of the whole URL. I still have to check youtube-dl documentation, but it doesn't change much.

I chose the download location (with some ln hacks) in such a way that the videoID.txt would end up in the same shared folder in dropbox.

I don't know Javascript, but I will review the bash part.

First, replace if [ $count != 0 ]; then with if [ "$count" -ne 0 ]; then.  The double quotes are a best practice though not crucial in this case (more on that later).  The -ne is for arithmetic comparisons; != is for string comparisons.

The next bit which jumped out at me was:

if [ $filename != mergedList ]; then
    rm $filename
fi

Two things here: One, unless you have a very specific reason not to, you should always put $variablenames in double quotes.  Otherwise special characters can break your script.  (You did the same thing earlier in the script with YTBSTR and count, but those don't really matter because due to the way you assigned their value, you can determine that it is safe.  Still, it wouldn't hurt to double quote them.)  In this context the lack of double quotes is not safe.

(Actually I read somewhere that putting the static value first is safer, i.e. [ mergedlist != "$filename" ], but I don't know enough to be sure if that is true or to explain why.)

Two: This line compares a string $filename which was gotten from a file glob for *.txt, with a static string mergedList.  The two will never, ever match.  $filename will always end in .txt because of the way it is defined.  So you may as well remove that check entirely!

Next, you should single quote the output of echo.  In this case your echo commands will work, but for instance if you remove the space after the ! you will get an error.  Single quoting disables all special character interpretation.

There are definitely some other things here to fix—for instance there seem to be some assumptions made about the file mergedList that could cause weird errors or even security holes—but the above is a start.


Wait for all resources to be loaded In my application I need some resources to be loaded and I have services to load each of them and then I need some point to know that all requests finished. First thought was to use $q.all with array of promises from that services. But it would be resolved only if all promises resolved which is now always the right case because some of them may be rejected. Finally I ended up with this code:

.service 'dataRepository', ($q, Categories, Items, Settings, Session) ->
    data: {}
    fetch: ->
        res = $q.defer()
        foo =
            categories: Categories.fetch()
            items: Items.fetch()
            settings: Settings.fetch()
            user: Session.fetch()

        cEnded = 0
        for k, p of foo
            p.then do (k) =>
                (result) =>
                    @data[k] = result

            p.finally do (k) =>
                =>
                    cEnded++
                    if cEnded is _.size foo
                        res.resolve @data
        res.promise

I can put result of dataRepository.fetch() in resolve of $urlRouterProvider of ui-router and in my controllers I can be sure that data loading finished.

But this is not looking like a good solution. So the question is, are there better ways to wait for the requests pool?

Actually I'm surprised there isn't a $q.some or so to do exactly that.

I think this is a good solution for the problem, though putting it in a separate function would be nice.  (Can't think of any reasons to not do it like this either.)


Check array contains element at compile time We have a modifyCoefficient(const char* name, int value) function that updates the value of a coefficient in a container. The names are known at compile time, they are read from an XML file in a pre-build step and stored in an array.
Usage: data.modifyCoefficient("ADAPTIVE", 1);
Compiler: MSVC 2017 v15.8

I would like to get a compile time error when the coefficient name does not exist.
With the following code that happens, but is there a way to do it without a macro?

#include <array>

#define COEFF(name) returnName<coefficientExists(name)>(name)

constexpr std::array<const char*, 3> COEFFICIENTS = { "VERSION", "CHANNELS", "ADAPTIVE" };

constexpr bool coefficientExists(const char* name)
{
    for (auto coefficientIndex = 0U; coefficientIndex < COEFFICIENTS.size(); ++coefficientIndex)
    {
        if (COEFFICIENTS[coefficientIndex] == name)
            return true;
    }
    return false;
}

template<bool CoefficientTest>
constexpr const char* returnName(const char* name)
{
    static_assert(CoefficientTest, "coefficient does not exist");
    return name;
}

int main()
{
    static_assert(coefficientExists("VERSION"), "should exist");
    static_assert(coefficientExists("TEST") == false, "should not exist");
    static_assert(COEFF("ADAPTIVE") == "ADAPTIVE", "should return name");
    COEFF("CHANNELS");
    // data.modifyCoefficient(COEFF("ADAPTIVE"), 1);
    return 0;
}

https://godbolt.org/z/kpGcMS

You have to compare values char by char, or even simpler change const char* to std::string_view make your code work.

Thanks to the deduction guides, you can just write std::array = ... and template parameters will be automatically deduced.

Also, you can simplify your loop using a "range-based for".
 If we generalize for other types of compile-time array, we get:

#include <array>
#include <string_view>

using namespace std::string_view_literals;
constexpr std::array COEFFICIENTS = { "VERSION"sv, "CHANNELS"sv, "ADAPTIVE"sv };

template <typename T, size_t N>
constexpr bool array_has(const std::array<T, N>& array, const T& value) {
  for (const auto& v : array) {
    if (value == v) return true;
  }
  return false;
}

constexpr bool coefficientExists(const std::string_view name)
{
    return array_has(COEFFICIENTS, name);
}

int main()
{
    static_assert(coefficientExists("VERSION"), "should exist");
    static_assert(!coefficientExists("TEST"), "should not exist");
}

With C++20 you can even do simpler:

#include <algorithm>
//...
template <typename T, size_t N>
constexpr bool array_has(const std::array<T, N> array, const T value) {
return std::any_of(array.begin(), array.end(), [value](auto current){ return current == value; });
}


Image-downloader/wallpaper setter I'm making an image-downloading app that sets the image as the device wallpaper. For this I used the class:

ImageDownloader.java

This class has a function which accepts a URL and an ImageView. It downloads and assigns the image found at the URL to the ImageView using an AsyncTask class defined within.

I managed to implement it as intended and wanted to extend its use to helping me set the devices wallpaper. This turned out to be pretty complicated but I managed with the following code in my MainActivity.java:

public class MainActivity extends Activity {
private final ImageDownloader mDownload = new ImageDownloader();
public static Bitmap bima=null;
public static WallpaperManager wm;

in onCreate:

 wm = WallpaperManager.getInstance(getApplicationContext());
    mDownload.download(url,imageView);

method defined in the MainActivity.Java:

public static void setbima(Bitmap bimu) {

    try {wm.setBitmap(bimu);} catch (Exception e) {}
}

Then I used my function in the ImageDownloader class' AsyncTask's onPostExecute like this:

MainActivity.setbima(bitmap);

Making use of the bitmap that was being passed to there by the AsyncTask class.

With the WallpaperManager object I wanted to make use of that bitmap, because its function .setBitmap() accepts bitmaps and puts the system wallpaper to that bitmap.

I am just wondering if my way of achieving this is optimal or is there a simpler way to have achieved this? It seems a very far-fetched way of doing this and I wouldn't be surprised if it is as I am a beginner programmer.

The system you have in place is efficient in the sense that it offloads the network-based work on to an AsyncTask, and the callback updates the wallpaper.

You don't give the details of your ImageLoader AsyncTask, but you could neaten a few things up by putting them in to there... and it would look something like:

public ImageLoader extends AsyncTask<String, Void, BitMap> {

    private final Context context;

    ImageLoader(Context context) {
        this.context = context;
    }

    public BitMap doInBackground(String urlpath) {
        // set the bitmap... do the work.
        return bitmap;
    }

    public void PostExecute(BitMap result) {
        try {
            WallpaperManager.getInstance(context).setBitmap(result);
        } catch (....) {
            ....
        }
    }

}

With the above task, it becomes a simple thing to do in the onCreate of the MainActivity:

new ImageDownloader(getApplicationContext()).execute(url);

That's the way to make it neat....


Simple class to let a thread make a clean work I was working on the last days with threads and I didn't want to use ugly methods like Abort(), etc.

So I did a simple class which does use one of the most performant and better alternative to Abort(). The class is named as CThread.cs which would stand for CleanThread.cs.

Class code:

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

public class CThread
{
    public List<CancellationTokenSource> CreatedThreads = new List<CancellationTokenSource>();

    private void MyFunction(Action callback, bool inLoop, int currentIndex)
    {
        if (inLoop)
        {
            while (!CreatedThreads[currentIndex].IsCancellationRequested)
            {
                callback();
            }
        }
        else { callback(); }
    }

    private int getLastIndex()
    {
        int index = 0;
        foreach (CancellationTokenSource item in CreatedThreads)
        {
            ++index;
        }

        return (index - 1);
    }

    public new void Start(Action callback, bool inLoop)
    {
        CancellationTokenSource tokenSource = new CancellationTokenSource();

        CreatedThreads.Add(tokenSource);
        int currentIndex = getLastIndex();
        Task task = Task.Run(() => MyFunction(callback, inLoop, currentIndex)); // use Task.Factory.StartNew for .net 4.0
    }

    public new void Stop(int threadIndex)
    {
        CreatedThreads[threadIndex].Cancel();
        Console.WriteLine("Thread has been stopped successfully! Press any key to continue...");
        Console.ReadKey();
    }
}

and finally, how I use it:

using System;

namespace CThreadExample
{
    internal class Program
    {
        private static void printFunction()
        {
            Console.WriteLine("Hello world!");
            System.Threading.Thread.Sleep(120);
        }

        private static void Main(string[] args)
        {
            CThread myThread = new CThread();
            myThread.Start(printFunction, true);

            // when the user presses any key the thread will be stopped
            Console.ReadKey();
            myThread.Stop(0); // stops the thread 0
        }
    }
}

Well, as you can see I'm not able right now to start threads using multiple parameters, but I didn't need to pass parameter to my thread.

Since I want to make everything clean, I accept any suggestion to improve this, also small suggestions for the code to make me able to pass one, two or more parameters and for cross-threading too (the Control.CheckForIllegalCrossThread = false; alternative way - so using delegates with Invoke() or BeginInvoke()).

This doesn't actually work as intended. You're using the CancellationTokenSource as a bool to decide whether to re-invoke the callback. That's not stopping a thread; that is not re-invoking the callback when it returns. The only reason why it appears to work for you is:

Your test callback is very short. Try inserting a long-running callback.
You print "Thread has been stopped successfully! Press any key to continue..." right after calling Cancel(). That statement is false; the only thing that has happened at that point is the CancellationTokenSource has been cancelled.

Other non-functional issues:

The CreatedThreads list doesn't hold threads, it holds CancellationTokenSources. Name the list appropriately.
Why is CreatedThreads public? It seems like something you wouldn't want the class to expose. Make it private.
This method is very strange:

private int getLastIndex()
{
    int index = 0;
    foreach (CancellationTokenSource item in CreatedThreads)
    {
        ++index;
    }

    return (index - 1);
}

Why does it not just return CreatedThreads.Count - 1 rather than iterating through the whole list? At that point there's no need for a method for it; Start can just do int currentIndex = CurrentThreads.Count - 1;

It is very awkward to have the Stop method take an index of the thread to stop, especially when an index was not supplied to or returned from Start. How is the caller of the method to know what index their thread is?

Finally I assume the only reason why you are calling Console methods in the CThread class is because you're using it for testing. Otherwise you definitely should not be doing that.


Sine function in C / C++ Due to software constraints, I cannot use the standard libraries, cmath, algorithm, templates, inline, or boost. I am also using standard C (ISO C99) such that array is not a reserved keyword like it is in Visual Studio.

Here is the custom sine, pow and factorial functions I wrote (assume they are all part of the same namespace and not using cmath). I looking for suggestions to improve robustness and efficiency. For example, both the pow and factorial are constrained by the int i in the for loops.

double factorial(double x)
{
    double result = 1;
    for (int i=1;i<=x;i++)
        result *= i;
    return result;
}

double pow(double x,double y)
{
    double result = 1;
    for (int i=0;i<y;i++)
        result *= x;
    return result;
}

double sine_taylor(double x,double n)
{
    double sine = x;
    bool isNeg;
    isNeg = true;
    for (double i=3;i<=n;i+=2)
    {
        if(isNeg)
        {
            sine -= pow(x,i)/factorial(i);
            isNeg = false;
        }
        else
        {
            sine += pow(x,i)/factorial(i);
            isNeg = true;
        }
    }
    return sine;
}

int main()
{
   const double pi = 3.14159265;
   double sineTaylor = sine_taylor(pi/2,7);
}

Not being able to use the standard libraries suggests you are doing embedded work.  A more typical approach for calculating sine in that situation would be to:

Translate angles from a 360 degree system to a 256 degree system;
Store sine values for all 256 possible degrees in a lookup table.

You lose a lot of accuracy, but you gain a lot of speed.